Other formats:
BibTeX
LaTeX
RIS
@inproceedings{792444,
author = {Hliněný, Petr and Ganian, Robert},
address = {United Kingdom},
booktitle = {International Workshop on Combinatorial Algorithms IWOCA 2008},
editor = {Mirka Miller and Koichi Wada},
keywords = {parameterized algorithm; rank-width; tree automaton; MSO logic},
howpublished = {tištěná verze "print"},
language = {eng},
location = {United Kingdom},
isbn = {978-1-904987-74-1},
pages = {4-15},
publisher = {Proceedings of the International Workshop on Combinatorial Algorithms 2008, College Publications},
title = {Automata Approach to Graphs of Bounded Rank-width},
url = {http://www.iwoca.org/iwoca2008},
year = {2008}
}
TY - JOUR
ID - 792444
AU - Hliněný, Petr - Ganian, Robert
PY - 2008
TI - Automata Approach to Graphs of Bounded Rank-width
PB - Proceedings of the International Workshop on Combinatorial Algorithms 2008, College Publications
CY - United Kingdom
SN - 9781904987741
KW - parameterized algorithm
KW - rank-width
KW - tree automaton
KW - MSO logic
UR - http://www.iwoca.org/iwoca2008
L2 - http://www.iwoca.org/iwoca2008
N2 - 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.
ER -
HLINĚNÝ, Petr and Robert GANIAN. Automata Approach to Graphs of Bounded Rank-width. In Mirka Miller and Koichi Wada. \textit{International Workshop on Combinatorial Algorithms IWOCA 2008}. United Kingdom: Proceedings of the International Workshop on Combinatorial Algorithms 2008, College Publications, 2008, p.~4-15. ISBN~978-1-904987-74-1.
|
