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. |
Další formáty:
BibTeX
LaTeX
RIS
|
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 |
Změnil | Změnil: RNDr. Robert Ganian, Ph.D., učo 99352. Změněno: 7. 1. 2011 11:43. |
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 |
VytisknoutZobrazeno: 13. 5. 2024 11:00