✦ LIBER ✦

Some APX-completeness results for cubic graphs

✍ Scribed by Paola Alimonti; Viggo Kann

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 122 KB
Volume: 237
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(98)00158-3

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Completeness results for graph isomorphi

Completeness results for graph isomorphism

✍ Birgit Jenner; Johannes Köbler; Pierre McKenzie; Jacobo Torán 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 239 KB

We prove that the graph isomorphism problem restricted to trees and to colored graphs with color multiplicities 2 and 3 is many-one complete for several complexity classes within NC 2 . In particular we show that tree isomorphism, when trees are encoded as strings, is NC 1 -hard under AC 0 -reductio

Some results on λ-valuation of graphs in

Some results on λ-valuation of graphs involving complete bipartite graphs

✍ Sze-Chin Shee 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 389 KB

Shee, S.-C., Some results on I-valuation of graphs involving complete bipartite graphs, Discrete Mathematics 87 (1991) 73-80. In this paper we show that a graph G obtained from a complete bipartite graph K,,, and a collection of q (cmax{m, n}) stars G, by joining the centre of G, to every vertex of

Sphericity exceeds cubicity for almost a

Sphericity exceeds cubicity for almost all complete bipartite graphs

✍ Hiroshi Maehara 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 209 KB

Completeness and conservative extension

Completeness and conservative extension results for some boolean relevant logics

✍ Steve Giambrone; Robert K. Meyer 📂 Article 📅 1989 🏛 Springer Netherlands 🌐 English ⚖ 767 KB

Some new results on 1-rotational 2-facto

Some new results on 1-rotational 2-factorizations of the complete graph

✍ Tommaso Traetta 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 129 KB 👁 1 views

## Abstract It is known that a necessary condition for the existence of a 1‐rotational 2‐factorization of the complete graph __K__~2__n__+1~ under the action of a group __G__ of order 2__n__ is that the involutions of __G__ are pairwise conjugate. Is this condition also sufficient? The complete ans

A P-Completeness Result for Visibility G

A P-Completeness Result for Visibility Graphs of Simple Polygons

✍ Jana Dietel; Hans-Dietrich Hecker 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 187 KB