@inproceedings{26c837a2b20a4912a95626f78867c381,
title = "On approximation properties of the independent set problem for degree 3 graphs",
abstract = "The main problem we consider in this paper is the Independent Set problem for bounded degree graphs. It is shown that the problem remains MAX SJVP-complete when the maximum degree is bounded by 3. Some related problems are also shown to be MAX SNP-complete at the lowest possible degree bounds. Next we study better poly-time approximation of the problem for degree 3 graphs, and improve the previously best ratio, |, to arbitrarily close to |. This result also provides improved poly-time approximation ratios, (Formula Presented), for odd degree B.",
author = "Piotr Berman and Toshihiro Fujito",
year = "1995",
month = jan,
day = "1",
doi = "10.1007/3-540-60220-8\_84",
language = "English (US)",
isbn = "3540602208",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "449--460",
editor = "Akl, \{Selim G.\} and Frank Dehne and J{\"o}rg-R{\"u}diger Sack and Nicola Santoro",
booktitle = "Algorithms and Data Structures - 4th International Workshop, WADS 1995, Proceedings",
address = "Germany",
note = "4th Workshop on Algorithms and Data Structures, WADS 1995 ; Conference date: 16-08-1995 Through 18-08-1995",
}