Approximation algorithms for the weighted independent set problem in sparse graphs

Akihisa Kako, Takao Ono*, Tomio Hirata, Magnús M. Halldórsson

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

18 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)617-626
Number of pages10
JournalDiscrete Applied Mathematics
Volume157
Issue number4
DOIs
Publication statusPublished - 28 Feb 2009

Other keywords

  • Approximation algorithm
  • Weighted degree
  • Weighted independent set problem

Fingerprint

Dive into the research topics of 'Approximation algorithms for the weighted independent set problem in sparse graphs'. Together they form a unique fingerprint.

Cite this