Enumerate and expand:: Improved algorithms for connected Vertex Cover and Tree Cover

被引：37

作者：

Moelle, Daniel ^{[1
]}

Richter, Stefan ^{[1
]}

Rossmanith, Peter ^{[1
]}

机构：

[1] Univ Aachen, Rhein Westfal TH Aachen, Dept Comp Sci, D-5100 Aachen, Germany

来源：

THEORY OF COMPUTING SYSTEMS | 2008年 / 43卷 / 02期

关键词：

exact algorithms; parameterized complexity; enumerate and expand; Vertex cover;

D O I：

10.1007/s00224-007-9089-3

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present a new method of solving graph problems related to VERTEX COVER by enumerating and expanding appropriate sets of nodes. As an application, we obtain dramatically improved runtime bounds for two variants of the VERTEX COVER problem. In the case of CONNECTED VERTEX COVER, we take the upper bound from O*(6k) to O*(2.7606(k)) without large hidden factors. For TREE COVER, we show a complexity of O*(3.2361(k)), improving over the previous bound of O*((2k)(k)). In the process, faster algorithms for solving subclasses of the Steiner tree problem on graphs are investigated.

引用

页码：234 / 253

页数：20

共 13 条

[1] An improved fixed-parameter algorithm for vertex cover [J].

Balasubramanian, R ;

Fellows, MR ;

Raman, V .

INFORMATION PROCESSING LETTERS, 1998, 65 (03) :163-168

[2] Refined memorization for vertex cover [J].

Chandran, LS ;

Grandoni, F .

INFORMATION PROCESSING LETTERS, 2005, 93 (03) :125-131

[3] Vertex Cover: Further observations and further improvements [J].

Chen, J ;

Kanj, IA ;

Jia, WJ .

JOURNAL OF ALGORITHMS, 2001, 41 (02) :280-301

[4]

CHEN J, 2005, TR05008 DEP U SCH CT

[5]

DOWNEY R, 1999, PARAMETERIZED COMPLE

[6]

Dreyfus S. E., 1972, Networks, V1, P195, DOI 10.1002/net.3230010302

[7]

Fernau H., 2002, Computing and Combinatorics. 8th Annual International Conference, COCOON 2002. Proceedings (Lecture Notes in Computer Science Vol.2387), P564

[8]

FERNAU H, 2006, TR2006210 U GLASG DE

[9]

Guo J, 2005, LECT NOTES COMPUT SC, V3608, P36

[10]

Mölle D, 2006, LECT NOTES COMPUT SC, V3884, P561

← 1 2 →