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

DOI10.1016/J.EJOR.2005.01.058MaRDI QIDQ2576274zbMATH OpenOpenAlexFDO

Authors 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

\(k\)-partite graphsapproximation algorithmscoloringcombinatorial optimizationgraph algorithmsweighted independent set

Mathematics Subject Classification ID

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

Recommendations

• Approximation algorithms for the weighted independent set problem in sparse graphs
• scientific article; zbMATH DE number 4011955
• Graph-Theoretic Concepts in Computer Science
• Approximation Algorithms for Some Graph Partitioning Problems
• On the approximability of the minimum weight t-partite clique problem
• Some approximation algorithms for the clique partition problem in weighted interval graphs
• Approximation algorithms for approximating graphs with bounded number of connected components
• Approximation algorithm for sparsest \(k\)-partitioning
• A class of bounded approximation algorithms for graph partitioning
• Parameterized Approximation Schemes Using Graph Widths

Cites work

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

This page was built for publication: A simple approximation algorithm for WIS based on the approximability in \(k\)-partite graphs

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