Better Polynomial Algorithms on Graphs of Bounded Rank-width.
| Authors | |
|---|---|
| Year of publication | 2009 |
| Type | Article in Proceedings |
| Conference | IWOCA 2009: International Workshop On Combinatorial Algorithms, Lecture Notes in Computer Science 5874 |
| MU Faculty or unit | |
| Citation | |
| Web | DOI |
| Doi | http://dx.doi.org/10.1007/978-3-642-10217-2 |
| Field | Informatics |
| Keywords | rank-width; parameterized algorithms; graphs |
| Description | Although there exist many polynomial algorithms for NP-hard problems running on a bounded clique-width expression of the input graph, there exists only little comparable work on such algorithms for rank-width. We believe that one reason for this is the somewhat obscure and hard-to-grasp nature of rank-decompositions. Nevertheless, strong arguments for using the rank-width parameter have been given by recent formalisms independently developed by Courcelle and Kante, by the authors, and by Bui-Xuan et al. This article focuses on designing formally clean and understandable "pseudopolynomial" (XP) algorithms solving "hard" problems (non-FPT) on graphs of bounded rank-width. Those include computing the chromatic number and polynomial or testing the Hamiltonicity of a graph and are extendable to many other problems. |
| Related projects: |