An FPT algorithm for Tree Deletion Set

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F13%3A00209344" target="_blank" >RIV/68407700:21240/13:00209344 - isvavai.cz</a>
Result on the web
<a href="http://link.springer.com/chapter/10.1007%2F978-3-642-36065-7_27" target="_blank" >http://link.springer.com/chapter/10.1007%2F978-3-642-36065-7_27</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-36065-7_27" target="_blank" >10.1007/978-3-642-36065-7_27</a>

Result language
angličtina
Original language name
An FPT algorithm for Tree Deletion Set
Original language description
We give a $5^k n^{O(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. Whileparameterized 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.
Czech name
—
Czech description
—

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2013
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISBN
978-3-642-36064-0
ISSN
0302-9743
e-ISSN
—
Number of pages
12
Pages from-to
286-297
Publisher name
Springer Science+Business Media
Place of publication
Berlin
Event location
Kharagpur
Event date
Feb 14, 2013
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)