Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>
Continuities
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
Others
Publication year
2012
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Lecture Notes in Computer Science
ISSN
0302-9743
e-ISSN
—
Volume of the periodical
7464
Issue of the periodical within the volume
Summer
Country of publishing house
DE - GERMANY
Number of pages
12
Pages from-to
348-359
UT code for WoS article
—
EID of the result in the Scopus database
—