On the treewidth of toroidal grids
On the treewidth of toroidal grids
复制标题
关于环形网格的树宽
DOI：
10.1016/j.dam.2015.06.027
复制
发表时间：
2016
影响因子：
1.1
通讯作者：
and Yota Otachi
中科院分区：
文献类型：
--
作者：
Yoshio Okamoto;Masashi Kiyomi;and Yota Otachi
许多网格图的图参数的研究，因为他们的算法后果。在这方面的一个重要概念是树宽。图的树宽是一个图的参数，用于度量图与树的接近程度。本文研究了环形网格的树宽，证明了n× n环形网格的树宽为2 n− 2或2 n− 1。然后，我们表明，这些界限是紧在某些情况下。为了显示下界，我们构造了高阶的荆棘。
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 n× n toroidal grid is either 2 n− 2 or 2 n− 1. We then show that these bounds are tight in some cases. To show the lower bounds, we construct brambles of high orders.