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

Varování

Publikace nespadá pod Ústav výpočetní techniky, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Název česky	Parsovací stromy a nástroje Myhill-Nerodova typu pro grafy omezené rank-width
Autoři	GANIAN Robert HLINĚNÝ Petr
Rok publikování	2010
Druh	Článek v odborném periodiku
Časopis / Zdroj	Discrete Applied Mathematics
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
www	DOI
Obor	Informatika
Klíčová slova	rank-width; parameterized algorithms; graphs
Popis	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.
Související projekty:	Vysoce paralelní a distribuované výpočetní systémy Využití strukturálních a šířkových parametrů v kombinatorice a algoritmické složitosti Strukturální teorie grafů a parametrizovaná složitost Parameterized Algorithms and Width measures on Graphs Rozsáhlé výpočetní systémy: modely, aplikace a verifikace