Publication details
Automata Approach to Graphs of Bounded Rank
-width
| Basic information | |
|---|---|
| Original title: | Automata Approach to Graphs of Bounded Rank-width |
| Authors: | Petr Hliněný, Robert Ganian |
| Further information | |
|---|---|
| Citation: | HLINĚNÝ, Petr - GANIAN, Robert. Automata Approach to Graphs of Bounded Rank-width. In Workshop MEMICS 2008. Brno : FI MU, 2008. ISBN 978-80-7355-082-0, p. 257-257. 17.11.2008, Znojmo. |
| Original language: | English |
| Field: | Informatika |
| WWW: |  conference |
| Type: | Article in Proceedings |
| Keywords: | parameterized algorithm; rank-width; tree automaton; MSO logic |
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:
