Some APX-completeness results for cubic graphs
2000 (English)In: Theoretical Computer Science, ISSN 0304-3975, Vol. 237, no 2-Jan, 123-134 p.Article in journal (Refereed) Published
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.
Place, publisher, year, edition, pages
2000. Vol. 237, no 2-Jan, 123-134 p.
computational complexity, NP-hard optimization problems, approximation, APX-completeness, cubic graphs, approximation classes, complexity
IdentifiersURN: urn:nbn:se:kth:diva-19747ISI: 000086979300006OAI: oai:DiVA.org:kth-19747DiVA: diva2:338439
QC 201005252010-08-102010-08-10Bibliographically approved