Approximation algorithms for the weighted independent set problem in sparse graphs

DOI10.1016/j.dam.2008.08.027zbMath1173.05352OpenAlexW2103011134MaRDI QIDQ1028454

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

Publication date: 30 June 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.08.027

zbMATH Keywords

approximation algorithmweighted independent set problemweighted degree

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

On vertex independence number of uniform hypergraphs, Unnamed Item, Unnamed Item

Cites Work

• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• Efficient bounds for the stable set, vertex cover and set packing problems
• On approximation properties of the independent set problem for low degree graphs
• Geometric algorithms and combinatorial optimization.
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A note on greedy algorithms for the maximum weighted independent set problem
• Improved approximations for weighted and unweighted graph problems
• Proof verification and the hardness of approximation problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Smallest-last ordering and clustering and graph coloring algorithms
• Approximate graph coloring by semidefinite programming
• Vertex packings: Structural properties and algorithms
• Low-degree Graph Partitioning via Local Search with Applications to Constraint Satisfaction, Max Cut, and Coloring
• Approximations of Weighted Independent Set and Hereditary Subset Problems