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

DOI10.1007/s10878-017-0127-zzbMath1383.90033OpenAlexW2601479054MaRDI QIDQ1679502

Zhipeng Cai, Weitian Tong, Dongjing Miao, Jian-Zhong Li

Publication date: 9 November 2017

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-017-0127-z

zbMATH Keywords

approximation algorithmvertex covercomplete multipartite graphconflict graph

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Improved upper bounds for vertex cover
• 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
• Depth-first search and the vertex cover problem
• Solving large FPT problems on coarse-grained parallel machines
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Vertex Cover in Graphs with Locally Few Colors
• Vertex Cover in Conflict Graphs: Complexity and a Near Optimal Approximation
• 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: Approximation for vertex cover in \(\beta\)-conflict graphs