You are here:
Publication details
Clique-width: When Hard Does Not Mean Impossible
Authors | |
---|---|
Year of publication | 2011 |
Type | Article in Proceedings |
Conference | 28th International Symposium on Theoretical Aspects of Computer Science STACS2011 |
MU Faculty or unit | |
Citation | |
web | |
Doi | http://dx.doi.org/10.4230/LIPIcs.STACS.2011.404 |
Field | Informatics |
Keywords | clique-width; parameterized algorithm; XP |
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, there still 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.\ also Minimum Leaf Spanning Tree) and Edge Disjoint Paths problems on digraphs of bounded clique-width with non-standard new approaches. |
Related projects: |