J 2013

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

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

Basic information

Original name

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

Name in Czech

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

Authors

GANIAN, Robert (840 United States of America, belonging to the institution), Petr HLINĚNÝ (203 Czech Republic, guarantor, belonging to the institution) and Jan OBDRŽÁLEK (203 Czech Republic, belonging to the institution)

Edition

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

Other information

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Netherlands

Confidentiality degree

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

Impact factor

Impact factor: 0.612

RIV identification code

RIV/00216224:14330/13:00065951

Organization unit

Faculty of Informatics

DOI

UT WoS

000314075000012

Keywords in English

rank-width; XP algorithm; coloring

Tags

Tags

International impact, Reviewed
Změněno: 3/4/2013 14:54, prof. RNDr. Petr Hliněný, Ph.D.

Abstract

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.

Links

GAP202/11/0196, research and development project
Name: Třídy dobře strukturovaných kombinatorických objektů, šířkové parametry a návrh efektivních algoritmů
Investor: Czech Science Foundation, Well-structured combinatorial classes, width parameters, and design of efficient algorithms
GC201/09/J021, research and development project
Name: Strukturální teorie grafů a parametrizovaná složitost
Investor: Czech Science Foundation, Structural graph theory and parameterized complexity