Other formats:
BibTeX
LaTeX
RIS
@article{1075308,
author = {Ganian, Robert and Hliněný, Petr and Obdržálek, Jan},
article_number = {3},
doi = {http://dx.doi.org/10.1016/j.ejc.2012.07.024},
keywords = {rank-width; XP algorithm; coloring},
language = {eng},
issn = {0195-6698},
journal = {European Journal of Combinatorics},
title = {Unified Approach to Polynomial Algorithms on Graphs of Bounded (bi-)Rank-width},
volume = {34},
year = {2013}
}
TY - JOUR
ID - 1075308
AU - Ganian, Robert - Hliněný, Petr - Obdržálek, Jan
PY - 2013
TI - Unified Approach to Polynomial Algorithms on Graphs of Bounded (bi-)Rank-width
JF - European Journal of Combinatorics
VL - 34
IS - 3
SP - 680-701
EP - 680-701
PB - Elsevier
SN - 01956698
KW - rank-width
KW - XP algorithm
KW - coloring
N2 - 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.
ER -
GANIAN, Robert, Petr HLINĚNÝ and Jan OBDRŽÁLEK. Unified Approach to Polynomial Algorithms on Graphs of Bounded (bi-)Rank-width. \textit{European Journal of Combinatorics}. Elsevier, 2013, vol.~34, No~3, p.~680-701. ISSN~0195-6698. Available from: https://dx.doi.org/10.1016/j.ejc.2012.07.024.
|
