Automata Approach to Graphs of Bounded Rank-width

HLINĚNÝ, Petr a Robert GANIAN. Automata Approach to Graphs of Bounded Rank-width. Online. In Workshop MEMICS 2008. Brno: FI MU, 2008. s. 257. ISBN 978-80-7355-082-0. [citováno 2024-04-23]

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) a Robert GANIAN (840 Spojené státy)
• Vydání: Brno, Workshop MEMICS 2008, s. 257-257, 2008.
• Nakladatel: FI MU

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í
• WWW: conference
• Kód RIV: RIV/00216224:14330/08:00027038
• Organizační jednotka: Fakulta informatiky
• ISBN: 978-80-7355-082-0
• 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

• MSM0021622419, záměr: Název: Vysoce paralelní a distribuované výpočetní systémy

Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy