Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization

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

zbMATH Keywords

approximation algorithmsprimal-dualgraph deletion problems

Mathematics Subject Classification ID

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