J 2013

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

GANIAN, Robert, Petr HLINĚNÝ a Jan OBDRŽÁLEK

Základní údaje

Originální název

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

Název česky

Sjednocený přístup k polynomiálním algoritmům na grafech omezené rank-width

Autoři

GANIAN, Robert (840 Spojené státy, domácí), Petr HLINĚNÝ (203 Česká republika, garant, domácí) a Jan OBDRŽÁLEK (203 Česká republika, domácí)

Vydání

European Journal of Combinatorics, Elsevier, 2013, 0195-6698

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Nizozemské království

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.612

Kód RIV

RIV/00216224:14330/13:00065951

Organizační jednotka

Fakulta informatiky

DOI

UT WoS

000314075000012

Klíčová slova anglicky

rank-width; XP algorithm; coloring

Štítky

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 3. 4. 2013 14:54, prof. RNDr. Petr Hliněný, Ph.D.

Anotace

V originále

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.

Návaznosti

GAP202/11/0196, projekt VaV
Název: Třídy dobře strukturovaných kombinatorických objektů, šířkové parametry a návrh efektivních algoritmů
Investor: Grantová agentura ČR, Třídy dobře strukturovaných kombinatorických objektů, šířkové parametry a návrh efektivních algoritmů
GC201/09/J021, projekt VaV
Název: Strukturální teorie grafů a parametrizovaná složitost
Investor: Grantová agentura ČR, Strukturální teorie grafů a parametrizovaná složitost