An FPT algorithm for Tree Deletion Set

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F13%3A00209343" target="_blank" >RIV/68407700:21240/13:00209343 - isvavai.cz</a>
Výsledek na webu
<a href="http://jgaa.info/getPaper?id=308" target="_blank" >http://jgaa.info/getPaper?id=308</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.7155/jgaa.00308" target="_blank" >10.7155/jgaa.00308</a>

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)}$ 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.
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)}$ 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.

Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
IN - Informatika
OECD FORD obor
—

Projekt
—
Návaznosti
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

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ů

Podobné výsledky(10)