Escape-width: Measuring "width" of digraphs

HLINĚNÝ, Petr a Jan OBDRŽÁLEK. Escape-width: Measuring "width" of digraphs. In Combinatorics, Graph Theory, Algorithms and Applications. Abstracts. 2006.

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 ORCID a Jan OBDRŽÁLEK

Vydání

Combinatorics, Graph Theory, Algorithms and Applications. Abstracts, 2006

---

Další údaje

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í

Odkazy

URL

Označené pro přenos do RIV

Ne

Organizační jednotka

Fakulta informatiky

Příznaky

Mezinárodní význam

---

Anotace

V originále

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.

Česky

Měření šířky orientovaných grafů

---

Návaznosti

GA201/05/0050, projekt VaV	Název: Strukturální vlastnosti a algoritmická složitost diskrétních problémů
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