Home Issues About JGAA Instructions for Authors
 
 
Special Issue on Selected Papers from the Seventh International Workshop on Algorithms and Computation, WALCOM 2013
DOI: 10.7155/jgaa.00308
An FPT algorithm for Tree Deletion Set
Vol. 17, no. 6, pp. 615-628, 2013. Regular paper.
Abstract We give a 5k nO(1) time fixed-parameter algorithm for determining whether a given undirected graph on n vertices has a subset of at most k vertices whose deletion results in a tree. Such a subset is a restricted form of a feedback vertex set. While parameterized complexity of feedback vertex set problem and several of its variations have been well studied, to the best of our knowledge, this is the first fixed-parameter algorithm for this version of feedback vertex set.
Submitted: May 2013.
Reviewed: September 2013.
Revised: October 2013.
Accepted: October 2013.
Final: October 2013.
Published: November 2013.
Communicated by Subir Kumar Ghosh
article (PDF)
BibTeX