A new approach for approximating node deletion problems

DOI10.1016/j.ipl.2003.08.005zbMath1178.68685OpenAlexW2074240671MaRDI QIDQ1029021

Amnon B. Barak, Michael S. Okun

Publication date: 9 July 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2003.08.005

zbMATH Keywords

approximation algorithmsnode deletion problemslocal ratio method

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Related Items (12)

Approximating Bounded Degree Deletion via Matroid Matching ⋮ Moderately exponential time algorithms for the maximum bounded-degree-1 set problem ⋮ Approximating power node-deletion problems ⋮ Approximation algorithm for (connected) bounded-degree deletion problem on unit disk graphs ⋮ Approximation algorithm for minimum weight connected-\(k\)-subgraph cover ⋮ PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs ⋮ A generalization of Nemhauser and Trotter's local optimization theorem ⋮ On the complexity of making a distinguished vertex minimum or maximum degree by vertex deletion ⋮ Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties ⋮ Unnamed Item ⋮ Approximating Partially Bounded Degree Deletion on Directed 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
• Unnamed Item
• The node-deletion problem for hereditary properties is NP-complete
• A unified approximation algorithm for node-deletion problems
• One for the price of two: a unified approach for approximating covering problems
• A threshold of ln n for approximating set cover
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
• The approximation of maximum subgraph problems

This page was built for publication: A new approach for approximating node deletion problems