Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
From MaRDI portal
Publication:2437764
DOI10.1016/j.tcs.2014.01.019zbMath1418.68245OpenAlexW2071170329MaRDI QIDQ2437764
Sounaka Mishra, Mrinal Kumar, N. Safina Devi, Saket Saurabh
Publication date: 13 March 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2014.01.019
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (11)
Linear‐time algorithms for eliminating claws in graphs ⋮ Analyzing the 3-path vertex cover problem in planar bipartite graphs ⋮ Maximum weight t-sparse set problem on vector-weighted graphs ⋮ On the \(d\)-claw vertex deletion problem ⋮ PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs ⋮ Quadratic vertex kernel for split vertex deletion ⋮ Improved approximation algorithms for path vertex covers in regular graphs ⋮ On the \(d\)-claw vertex deletion problem ⋮ Vertex deletion on split graphs: beyond 4-hitting set ⋮ An improved approximation for maximum \(k\)-dependent set on bipartite graphs ⋮ Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The node-deletion problem for hereditary properties is NP-complete
- A unified approximation algorithm for node-deletion problems
- The vertex cover \(P_3\) problem in cubic graphs
- Approximation Algorithms for Minimum Chain Vertex Deletion
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Node-Deletion Problems on Bipartite Graphs
- Graph Classes: A Survey
- Interactive proofs and the hardness of approximating cliques
- The approximation of maximum subgraph problems
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
This page was built for publication: Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
