Approximating Independent Sets in Degree-3 Graphs
Auteur : Piotr Berman
Date de publication : 1994
Éditeur : Pennsylvania State University, Department of Computer Science and Engineering, College of Engineering
Nombre de pages : 32
Résumé du livre
Abstract: "This paper presents an approximation algorithm for the Maximum Independent Set problem for graphs of degree bounded by 3. The performance ratio of the algorithm is arbitrarily close to 6/5 and it is based on Berman and Furer's heuristic. As a result, combined with our algorithm, their polynomial-time heuristic approximates a maximum independent set within ratio arbitrarily close to [delta]+3/5 in a graph of degree [delta]."