Unified Approach to Polynomial Algorithms on Graphs of Bounded (bi-)Rank-width

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 2013
Type Article in Periodical
Magazine / Source European Journal of Combinatorics
MU Faculty or unit

Faculty of Informatics

Citation
Doi http://dx.doi.org/10.1016/j.ejc.2012.07.024
Field Informatics
Keywords rank-width; XP algorithm; coloring
Description In this paper we develop new algorithmic machinery for solving hard problems on graphs of bounded rank-width and on digraphs of bounded bi-rank-width in polynomial (XP, to be precise) time. These include, particularly, graph coloring and chromatic polynomial problems, the Hamiltonian path and c-min-leaf outbranching, the directed cut, and more generally MSOL-partitioning problems on digraphs. Our focus on a formally clean and unified approach for the considered algorithmic problems is in contrast with many previous published XP algorithms running on graphs of bounded clique-width, which mostly used ad hoc techniques and ideas. The new contributions include faster algorithms for computing the chromatic number and the chromatic polynomial on graphs of bounded rank-width, and new algorithms for solving the defective coloring, the min-leaf outbranching, and the directed cut problems.
Related projects:

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