Some APX-completeness results for cubic graphs

被引：246

作者：

Alimonti, P ^{[1
]}

Kann, V

机构：

[1] Univ Roma La Sapienza, Dipartimento Informat & Sistemist, Rome, Italy

[2] Royal Inst Technol, Stockholm, Sweden

来源：

THEORETICAL COMPUTER SCIENCE | 2000年 / 237卷 / 1-2期

关键词：

computational complexity; NP-hard optimization problems; approximation; APX-completeness; cubic graphs;

D O I：

10.1016/S0304-3975(98)00158-3

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Four fundamental graph problems, Minimum vertex cover, Maximum independent set, Minimum dominating set and Maximum cut, are shown to be APX-complete even for cubic graphs. Therefore, unless P = NP, these problems do not admit any polynomial time approximation scheme on input graphs of degree bounded by three. (C) 2000 Elsevier Science B.V. All rights reserved.

引用

页码：123 / 134

页数：12

共 25 条

[1] THE COMPLEXITY AND APPROXIMABILITY OF FINDING MAXIMUM FEASIBLE SUBSYSTEMS OF LINEAR RELATIONS [J].

AMALDI, E ;

KANN, V .

THEORETICAL COMPUTER SCIENCE, 1995, 147 (1-2) :181-210

[2]

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

[3]

Arora S., 1992, Proceedings 33rd Annual Symposium on Foundations of Computer Science (Cat. No.92CH3188-0), P2, DOI 10.1109/SFCS.1992.267824

[4]

AUSIELLO G, 1998, IN PRESS APPROXIMATE

[5]

Bellare M, 1995, AN S FDN CO, P422, DOI 10.1109/SFCS.1995.492573

[6]

BERMAN P, 1994, PROCEEDINGS OF THE FIFTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P365

[7]

BERMAN P, 1995, LECT NOTES COMPUTER, V955

[8]

CRESCENZI F, 1995, SIRR9502 U ROM SAP D

[9] COMPLETENESS IN APPROXIMATION CLASSES [J].

CRESCENZI, P ;

PANCONESI, A .

INFORMATION AND COMPUTATION, 1991, 93 (02) :241-262

[10]

Crescenzi P, 1995, LECT NOTES COMPUT SC, V959, P539, DOI 10.1007/BFb0030875

← 1 2 3 →