Vertex cover in conflict graphs
DOI10.1016/j.tcs.2016.07.009zbMath1423.68354OpenAlexW2494376800MaRDI QIDQ2424881
Jian-Zhong Li, Xianmin Liu, Yingshu Li, Dongjing Miao
Publication date: 25 June 2019
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2016.07.009
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 (2)
Cites Work
- Ramsey numbers and an approximation algorithm for the vertex cover problem
- On the hardness of approximating minimum vertex cover
- Vertex covering by paths on trees with its applications in machine translation
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Vertex cover in conflict graphs