Automata Approach to 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

HLINĚNÝ Petr GANIAN Robert

Year of publication 2008
Type Article in Proceedings
Conference International Workshop on Combinatorial Algorithms IWOCA 2008
MU Faculty or unit

Faculty of Informatics

Citation
Web conference
Field Informatics
Keywords parameterized algorithm; rank-width; tree automaton; MSO logic
Description Rank-width is a rather new structural graph measure introduced by Oum and Seymour in 2003 in order to find an efficiently computable approximation of clique-width of a graph. Being a very nice graph measure indeed, the only serious drawback of rank-width was that it is virtually impossible to use a given rank-decomposition of a graph for running dynamic algorithms on it. We propose a new independent description of rank-decompositions of graphs using labeling parse trees which is, after all, mathematically equivalent to the recent algebraic graph-expression approach to rank-decompositions of Courcelle and Kant\'e [WG'07]. We then use our labeling parse trees to build a Myhill-Nerode-type formalism for handling restricted classes of graphs of bounded rank-width, and to directly prove that (an already indirectly known result) all graph properties expressible in MSO logic are decidable by finite automata running on the labeling parse trees.
Related projects:

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