On the treewidth of toroidal grids

详细信息    查看全文

• 作者：Masashi Kiyomi^a ; ^{masashi@yokohama-cu.ac.jp" class="auth_mail" title="E-mail the corresponding author} ; Yoshio Okamoto^b ; ^{okamotoy@uec.ac.jp" class="auth_mail" title="E-mail the corresponding author} ; Yota Otachi^c ; ^{otachi@jaist.ac.jp" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Treewidth ; Toroidal grid ; Bramble
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：10 January 2016
• 年：2016
• 卷：198
• 期：Complete
• 页码：303-306
• 全文大小：431 K

文摘

Many graph parameters of grid-like graphs are studied because of their algorithmic consequences. An important concept in this context is that of treewidth. Treewidth of graphs is a graph parameter for measuring how close a graph is to a tree. In this paper, we study the treewidth of toroidal grids and show that the treewidth of the d="mmlsi16" class="mathmlsrc">data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15003133&_mathId=si16.gif&_user=111111111&_pii=S0166218X15003133&_rdoc=1&_issn=0166218X&md5=dcbd0a2c03275d3441971e8a74adc3f3" title="Click to view the MathML source">n×ndden">de">$n\times n$ toroidal grid is either d="mmlsi171" class="mathmlsrc">data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15003133&_mathId=si171.gif&_user=111111111&_pii=S0166218X15003133&_rdoc=1&_issn=0166218X&md5=823f35ae332a52084e5c2f7202370266" title="Click to view the MathML source">2n−2dden">de">$2n-2$ or d="mmlsi168" class="mathmlsrc">data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15003133&_mathId=si168.gif&_user=111111111&_pii=S0166218X15003133&_rdoc=1&_issn=0166218X&md5=4deea8217a1f3b39d6e01d54fc7bd10d" title="Click to view the MathML source">2n−1dden">de">$2n-1$. We then show that these bounds are tight in some cases. To show the lower bounds, we construct brambles of high orders.