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., 2010, roč. 158, č. 1, s. 851-867. ISSN 0166-218X.

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 a Petr HLINĚNÝ ORCID

Vydání

Discrete Applied Mathematics, Amsterdam, Elsevier B.V. 2010, 0166-218X

---

Další údaje

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í

Odkazy

DOI

Impakt faktor

Impact factor: 0.822

Označené pro přenos do RIV

Ano

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

V originále

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.

Č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