A ckn 5-APPROXIMATION ALGORITHM FOR TREEWIDTH

被引：144

作者：

Bodlaender, Hans L. ^{[1
,2
]}

Drange, Pal Gronas ^{[3
]}

Dregi, Markus S. ^{[3
]}

Fomin, Fedor V. ^{[3
]}

Lokshtanov, Daniel ^{[3
]}

Pilipczuk, Micha L. ^{[4
]}

机构：

[1] Univ Utrecht, Dept Informat & Comp Sci, NL-3508 TC Utrecht, Netherlands

[2] Eindhoven Univ Technol, Dept Math & Comp Sci, POB 513, NL-5600 MB Eindhoven, Netherlands

[3] Univ Bergen, Dept Informat, N-5020 Bergen, Norway

[4] Univ Warsaw, Inst Informat, PL-00325 Warsaw, Poland

来源：

SIAM JOURNAL ON COMPUTING | 2016年 / 45卷 / 02期

基金：

欧洲研究理事会;

关键词：

algorithms; graphs; treewidth; approximation; fixed parameter tractability; BOUNDED TREE-WIDTH; PARALLEL ALGORITHMS; APPROXIMATION ALGORITHMS; SHORTEST PATHS; GRAPHS; PATHWIDTH; EFFICIENT; DIGRAPHS;

D O I：

10.1137/130947374

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：317 / 378

页数：62

共 43 条

[1]

Abraham Ittai., 2012, Proceedings of the 13th ACM Conference on Electronic Commerce, EC '12, P3

[2]

Abrahamson Karl, 1993, CONT MATH, P539

[3] Approximation Algorithms for Treewidth [J].

Amir, Eyal .

ALGORITHMICA, 2010, 56 (04) :448-479

[4]

[Anonymous], P 30 FOCS

[5]

[Anonymous], 1994, SPRINGER LECT NOTES

[6] COMPLEXITY OF FINDING EMBEDDINGS IN A K-TREE [J].

ARNBORG, S ;

CORNEIL, DG ;

PROSKUROWSKI, A .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1987, 8 (02) :277-284

[7]

Austrin P., 2012, LECT NOTES COMPUT SC, V7408, P13

[8]

Bodlaender H. L., 1993, Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, P226, DOI 10.1145/167088.167161

[9]

Bodlaender H. L., 1994, LECT NOTES COMPUTER, V790, P112

[10]

Bodlaender HL, 2013, LECT NOTES COMPUT SC, V7965, P196, DOI 10.1007/978-3-642-39206-1_17

← 1 2 3 4 5 →