A simple approximation algorithm for WIS based on the approximability in \(k\)-partite graphs

DOI10.1016/j.ejor.2005.01.058zbMath1096.90029OpenAlexW4299822411MaRDI QIDQ2576274

Jérôme Monnot

Publication date: 27 December 2005

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2005.01.058

zbMATH Keywords

combinatorial optimizationgraph algorithmscoloringapproximation algorithmsweighted independent set\(k\)-partite graphs

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Using stable sets to bound the chromatic number
• Efficient bounds for the stable set, vertex cover and set packing problems
• Three short proofs in graph theory
• Polynomial approximation and graph-coloring
• A note on greedy algorithms for the maximum weighted independent set problem
• Independent sets of maximum weight in (\(p,q\))-colorable graphs.
• Dioïds and semirings: Links to fuzzy sets and other applications
• Improved approximations for weighted and unweighted graph problems
• Vertex packings: Structural properties and algorithms
• Low-degree Graph Partitioning via Local Search with Applications to Constraint Satisfaction, Max Cut, and Coloring