Approximating Node-Deletion Problems for Matroidal Properties

DOI10.1006/JAGM.1998.0995zbMATH Open0928.68126OpenAlexW2016366379MaRDI QIDQ4240133FDOQ4240133

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

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

zbMATH Keywords

hereditary propertiesnode-deletion problemsuniformly sparse

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Cited In (9)

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

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)