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”

On Digraph Width Measures in Parameterized Algorithmics

Identifikátory výsledku

  • Kód výsledku v IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F09%3A00029749" target="_blank" >RIV/00216224:14330/09:00029749 - isvavai.cz</a>

  • Nalezeny alternativní kódy

    RIV/00216224:14330/09:00065869

  • Výsledek na webu

  • DOI - Digital Object Identifier

Alternativní jazyky

  • Jazyk výsledku

    angličtina

  • Název v původním jazyce

    On Digraph Width Measures in Parameterized Algorithmics

  • Popis výsledku v původním jazyce

    In contrast to undirected width measures (such as treewidth or clique-width), which have provided many important algorithmic applications, analogous measures for digraphs such as DAGwidth or Kelly-width do not seem so successful. Several recent papers, e.g. those of Kreutzer-Ordyniak, Dankelmann-Gutin-Kim, or Lampis-Kaouri-Mitsou, have given some evidence for this. We support this direction by showing that many quite different problems remain hard even on graph classes that are restricted very beyond simply having small DAG-width. To this end, we introduce new measures K-width and DAGdepth. On the positive side, we also note that taking Kanté's directed generalization of rank-width as a parameter makes many problems fixed parameter tractable.

  • Název v anglickém jazyce

    On Digraph Width Measures in Parameterized Algorithmics

  • Popis výsledku anglicky

    In contrast to undirected width measures (such as treewidth or clique-width), which have provided many important algorithmic applications, analogous measures for digraphs such as DAGwidth or Kelly-width do not seem so successful. Several recent papers, e.g. those of Kreutzer-Ordyniak, Dankelmann-Gutin-Kim, or Lampis-Kaouri-Mitsou, have given some evidence for this. We support this direction by showing that many quite different problems remain hard even on graph classes that are restricted very beyond simply having small DAG-width. To this end, we introduce new measures K-width and DAGdepth. On the positive side, we also note that taking Kanté's directed generalization of rank-width as a parameter makes many problems fixed parameter tractable.

Klasifikace

  • Druh

    D - Stať ve sborníku

  • CEP obor

    IN - Informatika

  • OECD FORD obor

Návaznosti výsledku

  • Projekt

    Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

  • Návaznosti

    S - Specificky vyzkum na vysokych skolach

Ostatní

  • Rok uplatnění

    2009

  • 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

    IWPEC 2009, Lecture Notes in Computer Science

  • ISBN

    978-3-642-11268-3

  • ISSN

  • e-ISSN

  • Počet stran výsledku

    13

  • Strana od-do

  • Název nakladatele

    Springer Verlag

  • Místo vydání

    Berlin

  • Místo konání akce

    Copenhagen, Denmark

  • Datum konání akce

    10. 9. 2009

  • Typ akce podle státní příslušnosti

    WRD - Celosvětová akce

  • Kód UT WoS článku