Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

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