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

zbMATH Keywords

approximation algorithmgraph coloringvertex 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 (2)

Maximum reachability preserved graph cut ⋮ Recognizing the tractability in big data computing

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