Approximation for vertex cover in \(\beta\)-conflict graphs
From MaRDI portal
Publication:1679502
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
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
