Graphs with Branchwidth at Most Three
Graphs with Branchwidth at Most Three
复制标题
分支宽度最多为 3 的图
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
D. Thilikos
中科院分区：
文献类型：
--
作者：
H. Bodlaender;D. Thilikos
在本文中，我们调查的结构图的分支宽度最多为3，以及算法来识别这样的图。我们证明了一个图的枝宽至多为3当且仅当它的树宽至多为3，并且不包含三维二元立方体图作为子图。一组四个图被证明是障碍集的一类图的分支宽度最多为3。此外，我们还给出了分支宽度不超过3的图的一组安全完备的归约规则。使用这个集合，给出了一个线性时间算法，该算法验证给定的图是否具有至多3个分支宽度，如果是，则输出最小宽度分支分解。
In this paper we investigate both the structure of graphs with branchwidth at most three, as well as algorithms to recognise such graphs. We show that a graph has branchwidth at most three if and only if it has treewidth at most three and does not contain the three-dimensional binary cube graph as a minor. A set of four graphs is shown to be the obstruction set for the class of graphs with branchwidth at most three. Moreover, we give a safe and complete set of reduction rules for the graphs with branchwidth at most three. Using this set, a linear time algorithm is given that verifies if a given graph has branchwidth at most three, and, if so, outputs a minimum width branch decomposition.