An FPT algorithm for tree deletion set

DOI10.1007/978-3-642-36065-7_27MaRDI QIDQ4914457zbMATH OpenOpenAlexFDO

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

Publication date 12 April 2013

Published in WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-36065-7_27

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

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

(6)

• Deleting to structured trees
• An FPT algorithm for Tree Deletion Set
• An FPT certifying algorithm for the vertex-deletion problem
• 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)
• Parameterized complexity of finding connected induced subgraphs

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 Q4914457)