Clique-width: When Hard Does Not Mean Impossible

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F11%3A00049978" target="_blank" >RIV/00216224:14330/11:00049978 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Clique-width: When Hard Does Not Mean Impossible

Popis výsledku v původním jazyce

In recent years, the parameterized complexity approach has lead to the introduction of many new algorithms and frameworks on graphs and digraphs of bounded clique-width and, equivalently, rank-width. However, despite intensive work on the subject, therestill exist well-established hard problems where neither a parameterized algorithm nor a theoretical obstacle to its existence are known. Our article is interested mainly in the digraph case, targeting the well-known Minimum Leaf Out-Branching (cf. alsoMinimum Leaf Spanning Tree) and Edge Disjoint Paths problems on digraphs of bounded clique-width with non-standard new approaches.

Název v anglickém jazyce

Clique-width: When Hard Does Not Mean Impossible

Popis výsledku anglicky

In recent years, the parameterized complexity approach has lead to the introduction of many new algorithms and frameworks on graphs and digraphs of bounded clique-width and, equivalently, rank-width. However, despite intensive work on the subject, therestill exist well-established hard problems where neither a parameterized algorithm nor a theoretical obstacle to its existence are known. Our article is interested mainly in the digraph case, targeting the well-known Minimum Leaf Out-Branching (cf. alsoMinimum Leaf Spanning Tree) and Edge Disjoint Paths problems on digraphs of bounded clique-width with non-standard new approaches.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

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

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2011

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ů

Název statě ve sborníku

28th International Symposium on Theoretical Aspects of Computer Science STACS2011

ISBN

978-3-939897-25-5

ISSN

1868-8969

e-ISSN

—

Počet stran výsledku

12

Strana od-do

404-415

Název nakladatele

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, LIPICS

Místo vydání

Dagstuhl, Germany

Místo konání akce

Dortmund, Germany

Datum konání akce

1. 1. 2011

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

WRD - Celosvětová akce

Kód UT WoS článku

—