Clique-width: When Hard Does Not Mean Impossible

Investor logo

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

GANIAN Robert HLINĚNÝ Petr OBDRŽÁLEK Jan

Year of publication 2011
Type Article in Proceedings
Conference 28th International Symposium on Theoretical Aspects of Computer Science STACS2011
MU Faculty or unit

Faculty of Informatics

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:

You are running an old browser version. We recommend updating your browser to its latest version.