| Údaje o výsledku |
| Identifikační kód | RIV/00216224:14330/12:00057892 |
| Název v původním jazyce | The DAG-width of directed graphs |
| Druh | J - Článek v odborném periodiku |
| Jazyk | eng - angličtina |
| Obor | IN - Informatika |
| Rok uplatnění | 2012 |
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů |
| Počet výskytů výsledku | 1 |
| Údaje z Hodnocení výsledků výzkumných organizací 2014 |
| Výsledek byl hodnocen v Pilíři I |
| Rozsah vyřazení výsledku | Tento výskyt výsledku není vyřazen |
| Zařazení výsledku v hodnocení | Jimp - Článek v impaktovaném časopise evidovaném ve Web of Science |
| Skupina oboru v hodnocení | 04 - Technické a informatické vědy |
| Konkrétní způsob(y) hodnocení výsledku | Výsledek hodnocený již v předchozím hodnocení, body se přebírají |
| Bodové ohodnocení | 59,710 |
| Faktor korekce | 90,8 % |
| Body (upravené podle přílohy č. 8 Metodiky) | 54,229 |
| Rozdělení výsledku mezi předkladatele |
| Organizace | Výzkumná organizace? | Podíl | Body | Body (upravené podle přílohy č. 8 Metodiky) |
|---|
| Masarykova univerzita / Fakulta informatiky | ano | 33,3 % | 19,903 | 18,076 |
|
| Tvůrci výsledku |
| Počet tvůrců celkem | 5 |
| Počet domácích tvůrců | 1 |
| Tvůrce | Berwanger Dietmar (státní příslušnost: DE - Spolková republika Německo) |
| Tvůrce | Dawar Anuj (státní příslušnost: GB - Spojené království Velké Británie a Severního Irska) |
| Tvůrce | Hunter Paul (státní příslušnost: AU - Australské společenství) |
| Tvůrce | Kreutzer Stephan (státní příslušnost: DE - Spolková republika Německo) |
| Tvůrce | Obdržálek Jan (státní příslušnost: CZ - Česká republika; A - domácí tvůrce; G - garant výsledku; vedidk: 3294099) |
| Údaje blíže specifikující výsledek |
| Popis v původní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 | tree-width; mu-calculus; model checking; parity games; decompositions; monotonicity; complexity; logic |
| Kód UT ISI | 000305492000005 |
| Rozsah stran | 900-923 |
| Název periodka | 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 |
| DOI výsledku | 10.1016/j.jctb.2012.04.004 |
| Údaje o tomto záznamu o výsledku |
| Předkladatel | Masarykova univerzita / Fakulta informatiky |
| Dodavatel | GA0 - Grantová agentura České republiky (GA ČR) |
| Rok sběru | 2013 |
| Systémové označení dodávky dat | RIV13-GA0-14330___/02:2 |
| Specifikace | RIV/00216224:14330/12:00057892!RIV13-GA0-14330___ |
| Kontrolní kód | [E5C389959C8F] |
| Jiný výskyt tohoto výsledku se v RIV nenachází |
| Odkazy na výzkumné aktivity, při jejichž řešení výsledek vznikl |
| Projekt | GC201/09/J021 - Strukturální teorie grafů a parametrizovaná složitost (2009-2010, GA0/GC) |