Approximating Node-Deletion Problems for Matroidal Properties

DOI10.1006/JAGM.1998.0995MaRDI QIDQ4240133zbMATH OpenOpenAlexFDO

Authors Toshihiro Fujito

Publication date 12 January 2000

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jagm.1998.0995

zbMATH Keywords

hereditary propertiesnode-deletion problemsuniformly sparse

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Recommendations

• A primal-dual approach to approximation of node-deletion problems for matroidal properties
• A unified local ratio approximation of node-deletion problems
• A unified approximation algorithm for node-deletion problems
• Node-and edge-deletion NP-complete problems
• The complexity of deletion problems for matroids

Cited in

(9)

• Randomized parameterized algorithms for \(P_2\)-packing and co-path packing problems
• Approximating bounded degree deletion via matroid matching
• Approximating power node-deletion problems
• Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies
• A unified local ratio approximation of node-deletion problems
• A primal-dual approach to approximation of node-deletion problems for matroidal properties
• The complexity of deletion problems for matroids
• A new approach for approximating node deletion problems
• GlobaL analysis of the deiete-contract recursion for graphs and matroids

This page was built for publication: Approximating Node-Deletion Problems for Matroidal Properties

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