Automata Approach to Graphs of Bounded Rank-width
| Authors | |
|---|---|
| Year of publication | 2008 |
| Type | Article in Proceedings |
| Conference | Workshop MEMICS 2008 |
| MU Faculty or unit | |
| 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: |