Approximation algorithms for minimum chain vertex deletion

DOI10.1007/978-3-642-19094-0_5MaRDI QIDQ3078376zbMATH OpenOpenAlexFDO

Authors Mrinal Kumar, Sounaka Mishra, N. Safina Devi, Saket Saurabh

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Approximating the Minimum Chain Completion problem
• Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
• An Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Covers in Bipartite Graphs
• Recognition and combinatorial optimization algorithms for bipartite chain graphs
• scientific article; zbMATH DE number 4135976

Cites work

• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
• Approximating the Minimum Chain Completion problem
• Computing the Minimum Fill-In is NP-Complete
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• Interactive proofs and the hardness of approximating cliques
• Node-Deletion Problems on Bipartite Graphs
• On the hardness of approximating minimization problems
• Optimization, approximation, and complexity classes
• The node-deletion problem for hereditary properties is NP-complete
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(5)

• The maximum cardinality cut problem in co-bipartite chain graphs
• Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
• A Note on the Minimum H-Subgraph Edge Deletion
• Recognition and combinatorial optimization algorithms for bipartite chain graphs
• Approximating the Minimum Chain Completion problem

This page was built for publication: Approximation algorithms for minimum chain vertex deletion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3078376)