Další formáty:
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Ý a Jan OBDRŽÁLEK. Unified Approach to Polynomial Algorithms on Graphs of Bounded (bi-)Rank-width. \textit{European Journal of Combinatorics}. Elsevier, 2013, roč.~34, č.~3, s.~680-701. ISSN~0195-6698. Dostupné z: https://dx.doi.org/10.1016/j.ejc.2012.07.024.
|