Automata Approach to Graphs of Bounded Rank-width

HLINĚNÝ, Petr a Robert GANIAN. Automata Approach to Graphs of Bounded Rank-width. In Mirka Miller and Koichi Wada. 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.

Základní údaje

• Originální název: Automata Approach to Graphs of Bounded Rank-width
• Název česky: Automatové zpracování grafů omezené rank-width
• Autoři: HLINĚNÝ, Petr (203 Česká republika, garant, domácí) a Robert GANIAN (840 Spojené státy, domácí).
• Vydání: United Kingdom, International Workshop on Combinatorial Algorithms IWOCA 2008, od s. 4-15, 12 s. 2008.
• Nakladatel: Proceedings of the International Workshop on Combinatorial Algorithms 2008, College Publications

Další údaje

• Originální jazyk: angličtina
• Typ výsledku: Stať ve sborníku
• Obor: 10201 Computer sciences, information science, bioinformatics
• Stát vydavatele: Japonsko
• Utajení: není předmětem státního či obchodního tajemství
• Forma vydání: tištěná verze "print"
• WWW: conference
• Kód RIV: RIV/00216224:14330/08:00025022
• Organizační jednotka: Fakulta informatiky
• ISBN: 978-1-904987-74-1
• Klíčová slova anglicky: parameterized algorithm; rank-width; tree automaton; MSO logic
• Štítky: MSO logic, parameterized algorithm, rank-width, tree automaton
• Příznaky: Mezinárodní význam, Recenzováno

Anotace

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.

Anotace česky

V příspěvku popisujeme nový nezávislý popis rankové dekompozice grafu pomocí speciálních parsovacích stromů. V tomto popisu následně ukazujeme ekvivalent Myhill-Nerodovy věty a jeho použití v návrhu algoritmů pro grafy omezené rank-width.

Návaznosti

• GA201/08/0308, projekt VaV: Název: Využití strukturálních a "šířkových" parametrů v kombinatorice a algoritmické složitosti

Investor: Grantová agentura ČR, Využití strukturálních a šířkových parametrů v kombinatorice a algoritmické složitosti

• 1M0545, projekt VaV: Název: Institut Teoretické Informatiky

Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky