Automata Approach to Graphs of Bounded Rank-width

HLINĚNÝ, Petr a Robert GANIAN. Automata Approach to Graphs of Bounded Rank-width. In Workshop MEMICS 2008. Brno: FI MU, 2008, s. 257. ISBN 978-80-7355-082-0.

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

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í

Odkazy

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

V originále

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.

Č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