An FPT algorithm for Tree Deletion Set

DOI10.7155/JGAA.00308MaRDI QIDQ2865021zbMATH OpenOpenAlexFDO

Authors Venkatesh Raman, Saket Saurabh, Ondřej Suchý

Publication date 28 November 2013

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.7155/jgaa.00308

zbMATH Keywords

fixed-parameter algorithmundirected graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• An FPT algorithm for tree deletion set
• Tree deletion set has a polynomial kernel (but no \(\mathrm {OPT}^{\mathcal O(1)}\) approximation)
• Tree deletion set has a polynomial kernel but no \(\mathrm{OPT}^\mathcal{O}(1)\) approximation)
• An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
• Computing and Combinatorics

Cited in

(8)

• Deleting to structured trees
• Parameterised algorithms for deletion to classes of DAGs
• An FPT certifying algorithm for the vertex-deletion problem
• Tree deletion set has a polynomial kernel (but no \(\mathrm {OPT}^{\mathcal O(1)}\) approximation)
• An FPT algorithm for tree deletion set
• Tree deletion set has a polynomial kernel but no \(\mathrm{OPT}^\mathcal{O}(1)\) approximation)
• Parameterized complexity of deletion to scattered graph classes
• Maintaining \(\mathrm{CMSO}_2\) properties on dynamic structures with bounded feedback vertex number

This page was built for publication: An FPT algorithm for Tree Deletion Set

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