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. |
Další formáty:
BibTeX
LaTeX
RIS
@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.
|