On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width

GANIAN, Robert a Petr HLINĚNÝ. On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width. Discrete Applied Mathematics. Amsterdam: Elsevier B.V., roč. 158, č. 1, s. 851-867. ISSN 0166-218X. 2010.

Základní údaje

• Originální název: On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
• Název česky: Parsovací stromy a nástroje Myhill-Nerodova typu pro grafy omezené rank-width
• Autoři: GANIAN, Robert (840 Spojené státy, domácí) a Petr HLINĚNÝ (203 Česká republika, garant, domácí).
• Vydání: Discrete Applied Mathematics, Amsterdam, Elsevier B.V. 2010, 0166-218X.

Další údaje

• Originální jazyk: angličtina
• Typ výsledku: Článek v odborném periodiku
• Obor: 10201 Computer sciences, information science, bioinformatics
• Stát vydavatele: Nizozemské království
• Utajení: není předmětem státního či obchodního tajemství
• WWW: DOI
• Impakt faktor: Impact factor: 0.822
• Kód RIV: RIV/00216224:14330/10:00043472
• Organizační jednotka: Fakulta informatiky
• UT WoS: 000276731700014
• Klíčová slova anglicky: rank-width; parameterized algorithms; graphs
• Příznaky: Mezinárodní význam, Recenzováno

Anotace

Rank-width is a structural graph measure introduced by Oum and Seymour and aimed at better handling of graphs of bounded clique-width. We propose a formal mathematical framework and tools for easy design of dynamic algorithms running directly on a rankdecomposition of a graph (on contrary to the usual approach which translates a rank decomposition into a clique-width expression, with a possible exponential jump in the parameter). The main advantage of this framework is a fine control over the runtime dependency on the rank-width parameter. Our new approach is linked to a work of Courcelle and Kanté [7] who first proposed algebraic expressions with a so-called bilinear graph product as a better way of handling rank-decompositions, and to a parallel recent research of Bui-Xuan, Telle and Vatshelle.

Anotace česky

Představujeme formální matematický framework pro snadnější návrh parametrizovaných algoritmů pro grafy omezené rank-width. Jeho hlavním přínosem je těsná kontrola časové složitosti vzhledem k parametru rank-width a přináší nové rychlejší algoritmy pro mnohé zajímavé problémy.

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

• GC201/09/J021, projekt VaV: Název: Strukturální teorie grafů a parametrizovaná složitost

Investor: Grantová agentura ČR, Strukturální teorie grafů a parametrizovaná složitost

• 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

• MUNI/A/0914/2009, interní kód MU: Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace (Akronym: SV-FI MAV)

Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty

• MUNI/E/0059/2009, interní kód MU: Název: Parameterized Algorithms and Width measures on Graphs

Investor: Masarykova univerzita, Parameterized Algorithms and Width measures on Graphs, Kat. E - Podpora výzkumné činnosti studentů v oborech lékařství, zdravotnictví, přírodovědy a informatiky - rozvojový projekt + specifický výzkum