Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419736 | Discrete Applied Mathematics | 2009 | 10 Pages |
Abstract
The approximability of the unweighted independent set problem has been analyzed in terms of sparseness parameters such as the average degree and inductiveness. In the weighted case, no corresponding results are possible for average degree, since adding vertices of small weight can decrease the average degree arbitrarily without significantly changing the approximation ratio. In this paper, we introduce two weighted measures, namely weighted average degree and weighted inductiveness, and analyze algorithms for the weighted independent set problem in terms of these parameters.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Akihisa Kako, Takao Ono, Tomio Hirata, Magnús M. Halldórsson,