Další formáty:
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 a 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, s.~4-15. ISBN~978-1-904987-74-1.
|