A simple \((2 + \epsilon)\)-approximation algorithm for split vertex deletion
DOI10.1016/j.ejc.2023.103844zbMATH Open1548.05309MaRDI QIDQ6612520
Tony Huynh, Matthew Drescher, Samuel Fiorini
Publication date: 30 September 2024
Published in: European Journal of Combinatorics (Search for Journal in Brave)
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Clique versus independent set
- Ramsey-type theorems
- The strong perfect graph theorem
- On universality of graphs with uniformly distributed edges
- The Erdős-Hajnal conjecture for paths and antipaths
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- 2-Approximating Feedback Vertex Set in Tournaments
- Induced Ramsey-type theorems
Related Items (1)
This page was built for publication: A simple \((2 + \epsilon)\)-approximation algorithm for split vertex deletion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6612520)
