Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10131336" target="_blank" >RIV/00216208:11320/12:10131336 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1007/978-3-642-32589-2_32" target="_blank" >http://dx.doi.org/10.1007/978-3-642-32589-2_32</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-32589-2_32" target="_blank" >10.1007/978-3-642-32589-2_32</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width
Popis výsledku v původním jazyce
The cluster vertex deletion number of a graph is the minimum number of its vertices whose deletion results in a disjoint union of complete graphs. This generalizes the vertex cover number, provides an upper bound to the clique-width and is related to thepreviously studied notion of the twin cover of the graph under consideration. We study the fixed parameter tractability of basic graph theoretic problems related to coloring and Hamiltonicity parameterized by cluster vertex deletion number. Our resultsshow that most of these problems remain fixed parameter tractable as well, and thus we push the borderline between tractability and intractability towards the clique-width parameter.
Název v anglickém jazyce
Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width
Popis výsledku anglicky
The cluster vertex deletion number of a graph is the minimum number of its vertices whose deletion results in a disjoint union of complete graphs. This generalizes the vertex cover number, provides an upper bound to the clique-width and is related to thepreviously studied notion of the twin cover of the graph under consideration. We study the fixed parameter tractability of basic graph theoretic problems related to coloring and Hamiltonicity parameterized by cluster vertex deletion number. Our resultsshow that most of these problems remain fixed parameter tractable as well, and thus we push the borderline between tractability and intractability towards the clique-width parameter.
Klasifikace
Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2012
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 periodika
Lecture Notes in Computer Science
ISSN
0302-9743
e-ISSN
—
Svazek periodika
7464
Číslo periodika v rámci svazku
Summer
Stát vydavatele periodika
DE - Spolková republika Německo
Počet stran výsledku
12
Strana od-do
348-359
Kód UT WoS článku
—
EID výsledku v databázi Scopus
—