Approximation algorithms for the weighted independent set problem in sparse graphs

DOI10.1016/J.DAM.2008.08.027MaRDI QIDQ1028454zbMATH OpenOpenAlexFDO

Authors A. Kako, Takao Ono, Tomio Hirata, 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)

Recommendations

• Graph-Theoretic Concepts in Computer Science
• Approximations of Weighted Independent Set and Hereditary Subset Problems
• scientific article; zbMATH DE number 1182757
• scientific article; zbMATH DE number 1405687
• A note on the approximation of a minimum-weight maximal independent set

Cites work

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

Cited in

(17)

• A simple approximation algorithm for WIS based on the approximability in \(k\)-partite graphs
• scientific article; zbMATH DE number 1405687 (Why is no real title available?)
• Maximum weight t-sparse set problem on vector-weighted graphs
• scientific article; zbMATH DE number 6297706 (Why is no real title available?)
• On vertex independence number of uniform hypergraphs
• Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary
• Approximations of Weighted Independent Set and Hereditary Subset Problems
• Graph-Theoretic Concepts in Computer Science
• Improved FPT Algorithms for Weighted Independent Set in Bull-Free Graphs
• Bilu-Linial stability, certified algorithms and the independent set problem
• Independent sets and vertex covers considered within the context of robust optimization
• Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm
• Approximating weighted neighborhood independent sets
• Approximation ratio of the min-degree greedy algorithm for maximum independent set on interval and chordal graphs
• Efficient computation of tolerances in the weighted independent set problem for trees
• A new distributed approximation algorithm for the maximum weight independent set problem
• Advice complexity of maximum independent set in sparse and bipartite graphs

This page was built for publication: Approximation algorithms for the weighted independent set problem in sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1028454)