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

(13)

• A new approach for approximating node deletion problems
• A unified approximation algorithm for node-deletion problems
• Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies
• Randomized parameterized algorithms for P₂-packing and co-path packing problems
• GlobaL analysis of the deiete-contract recursion for graphs and matroids
• A primal-dual approach to approximation of node-deletion problems for matroidal properties
• A unified local ratio approximation of node-deletion problems
• Approximating bounded degree deletion via matroid matching
• The complexity of deletion problems for matroids
• Approximating power node-deletion problems
• Polyhedral aspects of feedback vertex set and pseudoforest deletion set
• On minimum t-claw deletion in split graphs
• On deleting vertices to reduce density in graphs and supermodular functions

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)