Approximation Algorithms for Minimum Chain Vertex Deletion
From MaRDI portal
Publication:3078376
DOI10.1007/978-3-642-19094-0_5zbMath1317.68281OpenAlexW1534173609MaRDI QIDQ3078376
Sounaka Mishra, N. Safina Devi, Saket Saurabh, Mrinal Kumar
Publication date: 20 February 2011
Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-19094-0_5
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Approximating the Minimum Chain Completion problem
- The node-deletion problem for hereditary properties is NP-complete
- Optimization, approximation, and complexity classes
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Node-Deletion Problems on Bipartite Graphs
- Computing the Minimum Fill-In is NP-Complete
- On the hardness of approximating minimization problems
- Interactive proofs and the hardness of approximating cliques
- A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem