Clique-width: When Hard Does Not Mean Impossible

Result code in 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>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Clique-width: When Hard Does Not Mean Impossible
Original language description
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.
Czech name
—
Czech description
—

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Publication year
2011
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
28th International Symposium on Theoretical Aspects of Computer Science STACS2011
ISBN
978-3-939897-25-5
ISSN
1868-8969
e-ISSN
—
Number of pages
12
Pages from-to
404-415
Publisher name
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, LIPICS
Place of publication
Dagstuhl, Germany
Event location
Dortmund, Germany
Event date
Jan 1, 2011
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)