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; 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
• 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