Vertex Cover: Further observations and further improvements

被引：286

作者：

Chen, J ^{[1
]}

Kanj, IA

Jia, WJ

机构：

[1] Texas A&M Univ, Dept Comp Sci, College Stn, TX 77843 USA

[2] Depaul Univ, Sch CTI, Chicago, IL 60604 USA

[3] City Univ Hong Kong, Dept Comp Sci, Hong Kong, Hong Kong, Peoples R China

来源：

JOURNAL OF ALGORITHMS | 2001年 / 41卷 / 02期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1006/jagm.2001.1186

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Recently, there has been increasing interest and progress in lowering the worst-case time complexity for well-known NP-hard problems, particularly for the VERTEX COVER problem. In this paper, new properties for the VERTEX COVER problem are indicated, and several simple and new techniques are introduced, which lead to an improved algorithm of time O(kn + 1.2852(k)) for the problem. Our algorithm also induces improvement on previous algorithms for the INDEPENDENT SET problem on graphs of small degree. (C) 2001 Elsevier Science.

引用

页码：280 / 301

页数：22

共 24 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2]

[Anonymous], PARAMETERIZED COMPLE

[3]

[Anonymous], PROBABILISTIC ALGORI

[4]

[Anonymous], FEASIBLE MATH

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

Balasubramanian, R ;

Fellows, MR ;

Raman, V .

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

[6]

Bar-Yehuda R., 1985, ANN DISCRETE MATH, V25, P27, DOI DOI 10.1016/S0304-0208(08)73101-3

[7]

Beigel R., 1995, Proceedings. 36th Annual Symposium on Foundations of Computer Science (Cat. No.95CB35834), P444, DOI 10.1109/SFCS.1995.492575

[8]

Beigel R., 1999, P 10 ANN ACM SIAM S, P856

[9] NONDETERMINISM WITHIN P [J].

BUSS, JF ;

GOLDSMITH, J .

SIAM JOURNAL ON COMPUTING, 1993, 22 (03) :560-572

[10]

CHEN J, 1999, LECT NOTES COMPUTER, V1665, P313

← 1 2 3 →