Raman, Venkatesh ; Saurabh, Saket ; Suchý, Ondřej (2013) An FPT Algorithm for Tree Deletion Set Lecture Notes in Computer Science, 7748 . pp. 286-297. ISSN 0302-9743
Full text not available from this repository.
Official URL: http://doi.org/10.1007/978-3-642-36065-7_27
Related URL: http://dx.doi.org/10.1007/978-3-642-36065-7_27
Abstract
We give a 5knO(1) 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.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Springer-Verlag. |
| ID Code: | 123446 |
| Deposited On: | 16 Sep 2021 12:06 |
| Last Modified: | 16 Sep 2021 12:06 |
Repository Staff Only: item control page
