AbstractA graph is

d-claw free if no node hasddistinct independent neighbors. In the most usual applications, the nodes of this graph form a family of sets with fewer thandelements, and the edges indicate overlapping pairs of sets. Consequently, an independent set in the graph is a packing in our family of sets. In this paper we consider the following problem. Given is ad-claw free graph G = (V,E,w) wherew: V -> R+. We describe an algorithm with running time polynomial in |V|^{d}that finds an independent setAsuch thatw(A, where^{*})/w(A) <= d/2A^{*}is an independent that maximizesw(A. The previous best polynomial time approximation algorithm obtained^{*})w(A.^{*})/w(A) <= 2d/3

Categories and Subject Descriptors: F.2 [Analysis of Algorithms and Problem Complexity]; G.2.2 [Discrete Mathematics]: Graph Theory

Additional Key Words and Phrases: approximation algorithms, maximum independent set, node weights

Selected references

- Magnús M. Halldórsson. Approximating discrete collections via local improvements. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 160-169, San Francisco, California, 22-24 January 1995.