The DAG-width of directed graphs

J 2012

The DAG-width of directed graphs

BERWANGER, Dietmar, Anuj DAWAR, Paul HUNTER, Stephan KREUTZER, Jan OBDRŽÁLEK et. al.

Základní údaje

Originální název

The DAG-width of directed graphs

Autoři

BERWANGER, Dietmar (276 Německo), Anuj DAWAR (826 Velká Británie a Severní Irsko), Paul HUNTER (36 Austrálie), Stephan KREUTZER (276 Německo) a Jan OBDRŽÁLEK (203 Česká republika, garant, domácí)

Vydání

Journal of Combinatorial Theory, Ser B, Amsterdam, Elsevier B.V. 2012, 0095-8956

Další údaje

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í

Impakt faktor

Impact factor: 0.845

Kód RIV

RIV/00216224:14330/12:00057892

Organizační jednotka

Fakulta informatiky

DOI

http://dx.doi.org/10.1016/j.jctb.2012.04.004

UT WoS

000305492000005

Klíčová slova anglicky

tree-width; mu-calculus; model checking; parity games; decompositions; monotonicity; complexity; logic

Štítky

formela-journal

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 5. 12. 2012 10:31, doc. Mgr. Jan Obdržálek, PhD.

Anotace

V originále

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. A consequence we obtain is that certain NP-complete problems such as Hamiltonicity and disjoint paths are polynomial-time computable on graphs of bounded DAG-width.

Návaznosti

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

Citovat

BERWANGER, Dietmar, Anuj DAWAR, Paul HUNTER, Stephan KREUTZER a Jan OBDRŽÁLEK. The DAG-width of directed graphs. Journal of Combinatorial Theory, Ser B. Amsterdam: Elsevier B.V., 2012, roč. 102, č. 4, s. 900-923. ISSN 0095-8956. Dostupné z: https://dx.doi.org/10.1016/j.jctb.2012.04.004.

@article{1076197,
   author = {Berwanger, Dietmar and Dawar, Anuj and Hunter, Paul and Kreutzer, Stephan and Obdržálek, Jan},
   article_location = {Amsterdam},
   article_number = {4},
   doi = {http://dx.doi.org/10.1016/j.jctb.2012.04.004},
   keywords = {tree-width; mu-calculus; model checking; parity games; decompositions; monotonicity; complexity; logic},
   language = {eng},
   issn = {0095-8956},
   journal = {Journal of Combinatorial Theory, Ser B},
   title = {The DAG-width of directed graphs},
   volume = {102},
   year = {2012}
}

TY  - JOUR
ID  - 1076197
AU  - Berwanger, Dietmar - Dawar, Anuj - Hunter, Paul - Kreutzer, Stephan - Obdržálek, Jan
PY  - 2012
TI  - The DAG-width of directed graphs
JF  - Journal of Combinatorial Theory, Ser B
VL  - 102
IS  - 4
SP  - 900-923
EP  - 900-923
PB  - Elsevier B.V.
SN  - 00958956
KW  - tree-width
KW  - mu-calculus
KW  - model checking
KW  - parity games
KW  - decompositions
KW  - monotonicity
KW  - complexity
KW  - logic
N2  - 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. A consequence we obtain is that certain NP-complete problems such as Hamiltonicity and disjoint paths are polynomial-time computable on graphs of bounded DAG-width.
ER  -

BERWANGER, Dietmar, Anuj DAWAR, Paul HUNTER, Stephan KREUTZER a Jan OBDRŽÁLEK. The DAG-width of directed graphs. \textit{Journal of Combinatorial Theory, Ser B}. Amsterdam: Elsevier B.V., 2012, roč.~102, č.~4, s.~900-923. ISSN~0095-8956. Dostupné z: https://dx.doi.org/10.1016/j.jctb.2012.04.004.

Podrobný výpis o publikaci