HLINĚNÝ, Petr a Jan OBDRŽÁLEK. Escape-width: Measuring "width" of digraphs. Online. In Combinatorics, Graph Theory, Algorithms and Applications. Abstracts. 2006, [citováno 2024-04-24]
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název Escape-width: Measuring "width" of digraphs
Název česky Měření šířky orientovaných grafů
Autoři HLINĚNÝ, Petr a Jan OBDRŽÁLEK
Vydání Combinatorics, Graph Theory, Algorithms and Applications. Abstracts, 2006.
Další údaje
Originální jazyk angličtina
Typ výsledku Konferenční abstrakt
Obor 10101 Pure mathematics
Stát vydavatele Česká republika
Utajení není předmětem státního či obchodního tajemství
WWW URL
Organizační jednotka Fakulta informatiky
Příznaky Mezinárodní význam
Změnil Změnila: Ing. Dana Komárková, učo 1475. Změněno: 27. 6. 2008 12:28.
Anotace
The question of finding an extension of the ordinary tree-width notion to directed graphs, with similarly nice algorithmic properties, seems to be a challenging problem. Nowadays there exist two competing extensions -- the older directed tree-width by Johnson, Robertson, Seymour, and Thomas, and the recent DAG-width which has been independently proposed by the second author and Berwanger, Dawar, Hunter and Kreutzer. In this paper we introduce yet another extension that naturally arises by introducing orientation of edges in one of alternative definitions of ordinary tree-width, and we show that it is closely related to DAG-width.
Anotace česky
Měření šířky orientovaných grafů
Návaznosti
GA201/05/0050, projekt VaVNázev: Strukturální vlastnosti a algoritmická složitost diskrétních problémů
MSM0021622419, záměrNá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
VytisknoutZobrazeno: 24. 4. 2024 06:35