Geodesic
An FPT algorithm for Tree Deletion Set
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Seventh International Workshop on Algorithms and Computation, WALCOM 2013 , Tome 17 (2013) no. 6, pp. 615-628.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00308
Keywords: Feedback Vertex Set, Tree, FPT Algorithms, Graph Connectivity, Parameterized Complexity 
@article{JGAA_2013_17_6_a2,
     author = {Venkatesh Raman and Saket Saurabh and Ond\v{r}ej Such\'y},
     title = {An {FPT} algorithm for {Tree} {Deletion} {Set}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {615--628},
     publisher = {mathdoc},
     volume = {17},
     number = {6},
     year = {2013},
     doi = {10.7155/jgaa.00308},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00308/}
}
TY  - JOUR
AU  - Venkatesh Raman
AU  - Saket Saurabh
AU  - Ondřej Suchý
TI  - An FPT algorithm for Tree Deletion Set
JO  - Journal of Graph Algorithms and Applications
PY  - 2013
SP  - 615
EP  - 628
VL  - 17
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00308/
DO  - 10.7155/jgaa.00308
LA  - en
ID  - JGAA_2013_17_6_a2
ER  - 
%0 Journal Article
%A Venkatesh Raman
%A Saket Saurabh
%A Ondřej Suchý
%T An FPT algorithm for Tree Deletion Set
%J Journal of Graph Algorithms and Applications
%D 2013
%P 615-628
%V 17
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00308/
%R 10.7155/jgaa.00308
%G en
%F JGAA_2013_17_6_a2
Venkatesh Raman; Saket Saurabh; Ondřej Suchý. An FPT algorithm for Tree Deletion Set. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Seventh International Workshop on Algorithms and Computation, WALCOM 2013
					, Tome 17 (2013) no. 6, pp. 615-628. doi : 10.7155/jgaa.00308. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00308/

Cité par Sources :