A O(c^k n) 5-Approximation Algorithm for Treewidth
A O(c^k n) 5-Approximation Algorithm for Treewidth
复制标题
树宽的 O(c^k n) 5 近似算法
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
D. Lokshtanov
中科院分区：
文献类型：
--
作者：
H. Bodlaender;Markus S. Dregi;F. Fomin;D. Lokshtanov
我们给出了一个算法，对于输入的n点图G和整数k>；0，在时间2^[O(K)]n输出G的树宽大于k，或者给出G的树分解的最大宽度为5k+4。这是第一个提供树宽的恒因子近似的算法，它在时间上以k为单指数，n为线性。基于Treewidth的计算是许多算法的子程序。我们的算法可以用来加速许多这类算法的工作时间，使其在树宽上是单指数的，在输入大小上是线性的。
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.