A simple approximation algorithm for WIS based on the approximability in k-partite graphs
Monnot, Jérôme (2006), A simple approximation algorithm for WIS based on the approximability in k-partite graphs, European Journal of Operational Research, 171, 1, p. 346-348. http://dx.doi.org/10.1016/j.ejor.2005.01.058
TypeArticle accepté pour publication ou publié
Journal nameEuropean Journal of Operational Research
MetadataShow full item record
Abstract (EN)In this note, simple approximation algorithms for the weighted independent set problem are presented with a performance ratio depending on Δ(G). These algorithms do not improve the best approximation algorithm known so far for this problem but they are of interest because of their simplicity. Precisely, we show how an optimum weighted independent set in bipartite graphs and a ρ-approximation of WIS in k-partite graphs respectively allows to obtain a 2/Δ(G)-approximation and a k/Δ(G)ρ -approximation in general graphs. Note that the ratio 2/Δ(G)is the best bound known for the particular cases Δ(G) = 3 or Δ(G) = 4.
Subjects / KeywordsColoring; Graph algorithms; Approximation algorithms; Combinatorial optimization; k-partite graphs; Weighted independent set
Showing items related by title and author.
Complexity and Approximation Results for the Connected Vertex Cover Problem in Graphs and Hypergraphs Monnot, Jérôme; Gourvès, Laurent; Escoffier, Bruno (2010) Article accepté pour publication ou publié