A ckn 5-APPROXIMATION ALGORITHM FOR TREEWIDTH
A ckn 5-APPROXIMATION ALGORITHM FOR TREEWIDTH
复制标题
DOI：
10.1137/130947374
复制
发表时间：
2016-01-01
影响因子：
1.6
通讯作者：
Pilipczuk, Micha L.
中科院分区：
文献类型：
--
作者：
Bodlaender, Hans L.;Drange, Pal Gronas;Pilipczuk, Micha L.
我们给出了一个算法，对于输入的n阶图G且整数k > 0，在时间2（O（k））n内，要么输出G的树宽大于k，要么给出G的树分解，其宽度最多为5k + 4。这是第一个提供树宽的常数因子近似的算法，它在时间上运行，在k中是单指数的，在n中是线性的。基于树宽的计算是许多算法的子程序。我们的算法可以用来加速许多这样的算法，在时间上是单指数的树宽和线性的输入大小。
We give an algorithm that for an input n-vertex graph G and integer k > 0, in time 2(O(k))n, either outputs that the treewidth of G is larger than k, or gives a tree decomposition of G of width at most 5k + 4. This is the first algorithm providing a constant factor approximation for treewidth which runs in time single exponential in k and linear in n. Treewidth-based computations are subroutines of numerous algorithms. Our algorithm can be used to speed up many such algorithms to work in time which is single exponential in the treewidth and linear in the input size.