Vertex Cover in Conflict Graphs: Complexity and a Near Optimal Approximation

DOI10.1007/978-3-319-26626-8_29zbMath1473.68124OpenAlexW2395653148MaRDI QIDQ3467859

Xianmin Liu, Dongjing Miao, Hong Gao, Jian-Zhong Li

Publication date: 5 February 2016

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-26626-8_29

zbMATH Keywords

approximation algorithmvertex covercomplete multipartite graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (1)

Approximation for vertex cover in \(\beta\)-conflict graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Ramsey numbers and an approximation algorithm for the vertex cover problem
• On the hardness of approximating minimum vertex cover
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• A better approximation ratio for the vertex cover problem
• The Design of Approximation Algorithms
• Vertex Cover in Graphs with Locally Few Colors
• Divide-and-Conquer Approximation Algorithm for Vertex Cover
• Vertex packings: Structural properties and algorithms
• Some optimal inapproximability results
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph

This page was built for publication: Vertex Cover in Conflict Graphs: Complexity and a Near Optimal Approximation