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: |