An FPT algorithm for Tree Deletion Set
Identifikátory výsledku
Kód výsledku v 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>
Výsledek na webu
<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>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
An FPT algorithm for Tree Deletion Set
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
An FPT algorithm for Tree Deletion Set
Popis výsledku anglicky
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.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
—
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2013
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
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
—
Počet stran výsledku
12
Strana od-do
286-297
Název nakladatele
Springer Science+Business Media
Místo vydání
Berlin
Místo konání akce
Kharagpur
Datum konání akce
14. 2. 2013
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—