On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width

Investor logo

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

GANIAN Robert HLINĚNÝ Petr

Year of publication 2010
Type Article in Periodical
Magazine / Source Discrete Applied Mathematics
MU Faculty or unit

Faculty of Informatics

Citation
Web DOI
Field Informatics
Keywords rank-width; parameterized algorithms; graphs
Description Rank-width is a structural graph measure introduced by Oum and Seymour and aimed at better handling of graphs of bounded clique-width. We propose a formal mathematical framework and tools for easy design of dynamic algorithms running directly on a rankdecomposition of a graph (on contrary to the usual approach which translates a rank decomposition into a clique-width expression, with a possible exponential jump in the parameter). The main advantage of this framework is a fine control over the runtime dependency on the rank-width parameter. Our new approach is linked to a work of Courcelle and Kanté [7] who first proposed algebraic expressions with a so-called bilinear graph product as a better way of handling rank-decompositions, and to a parallel recent research of Bui-Xuan, Telle and Vatshelle.
Related projects:

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