The DAG-width of directed graphs (2012)výskyt výsledku
| Identifikační kód | RIV/00216224:14330/12:00057892 |
|---|---|
| Název v anglickém jazyce | The DAG-width of directed graphs |
| Druh | J - Článek v odborném periodiku |
| Jazyk | eng - angličtina |
| Obor - skupina | I - Informatika |
| Obor | IN - Informatika |
| Rok uplatnění | 2012 |
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
| Počet výskytů výsledku | 1 |
| Počet tvůrců celkem | 5 |
| Počet domácích tvůrců | 1 |
| Výčet všech uvedených jednotlivých tvůrců | Dietmar Berwanger (státní příslušnost: DE - Spolková republika Německo) Anuj Dawar (státní příslušnost: GB - Spojené království Velké Británie a Severního Irska) Paul Hunter (státní příslušnost: AU - Austrálie) Stephan Kreutzer (státní příslušnost: DE - Spolková republika Německo) Jan Obdržálek (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 3294099) |
| Popis výsledku v anglickém jazyce | Tree-width is a well-known metric on undirected graphs that measures how tree-like a graph is and gives a notion of graph decomposition that proves useful in algorithm design. Tree-width can be characterised by a graph searching game where a number of cops attempt to capture a robber. We consider the natural adaptation of this game to directed graphs and show that monotone strategies in the game yield a measure, called DAG-width, that can be seen to describe how close a directed graph is to a directed acyclic graph (DAG). We also provide an associated decomposition and show how it is useful for developing algorithms on directed graphs. In particular, we show that the problem of determining the winner of a parity game is solvable in polynomial time on graphs of bounded DAG-width. We also consider the relationship between DAG-width and other connectivity measures such as directed tree-width and path-width. |
| Klíčová slova oddělená středníkem | tree-width; mu-calculus; model checking; parity games; decompositions; monotonicity; complexity; logic |
| Stránka www, na které se nachází výsledek | - |
| DOI výsledku | 10.1016/j.jctb.2012.04.004 |
Údaje o výsledku v závislosti na druhu výsledku
| Název periodika | Journal of Combinatorial Theory, Ser B |
|---|---|
| ISSN | 0095-8956 |
| Svazek periodika | 102 |
| Číslo periodika v rámci uvedeného svazku | 4 |
| Stát vydavatele periodika | NL - Nizozemsko |
| Počet stran výsledku | 24 |
| Strana od-do | 900-923 |
| Kód UT WoS článku podle Web of Science | 000305492000005 |
| EID výsledku v databázi Scopus | - |
Ostatní informace o výsledku
| Předkladatel | Masarykova univerzita / Fakulta informatiky |
|---|---|
| Dodavatel | GA0 - Grantová agentura České republiky (GA ČR) |
| Rok sběru | 2013 |
| Specifikace | RIV/00216224:14330/12:00057892!RIV13-GA0-14330___ |
| Datum poslední aktualizace výsledku | 04.09.2013 |
| Kontrolní číslo | 43537000 |
Odkazy na výzkumné aktivity, při jejichž řešení výsledek vznikl
| Projekt podporovaný GA ČR v programu GC | GC201/09/J021 - Strukturální teorie grafů a parametrizovaná složitost (2009 - 2010) |
|---|