A linear-time ie algorithm for finding three-decompositions of small treewidth
A linear-time ie algorithm for finding three-decompositions of small treewidth
复制标题
DOI：
10.1137/s0097539793251219
复制
发表时间：
1996-12-01
影响因子：
1.6
通讯作者：
Bodlaender, HL
中科院分区：
文献类型：
--
作者：
Bodlaender, HL
在本文中，我们针对常数 k 给出了一个线性时间算法，给定图 G = (V, E)，确定 G 的树宽是否至多为 k，如果是，则找到树宽至多为 k 的 G 的树分解。结果是，不包含所有平面图的每个小闭类图都有线性时间识别算法。另一个结果是，当我们寻找路径宽度为某个常数 k 的路径分解时，类似的结果成立。
In this paper, we give for constant k a linear-time algorithm that, given a graph G = (V, E), determines whether the treewidth of G is at most k and, if so, finds a tree-decomposition of G with treewidth at most k. A consequence is that every minor-closed class of graphs that does not contain all planar graphs has a linear-time recognition algorithm. Another consequence is that a similar result holds when we look instead for path-decompositions with pathwidth at mast some constant k.