The dag-width of directed graphs
DOI10.1016/J.JCTB.2012.04.004zbMATH Open1246.05065OpenAlexW2127618440WikidataQ58215516 ScholiaQ58215516MaRDI QIDQ444380FDOQ444380
Authors: Dietmar Berwanger, Anuj Dawar, Paul Hunter, Stephan Kreutzer, Jan Obdržálek 
Publication date: 14 August 2012
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jctb.2012.04.004
Recommendations
graph searching gamesparity gamesstructural graph theorydigraph algorithmsdirected graph decompositions
Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Games on graphs (graph-theoretic aspects) (05C57) Graph minors (05C83)
Cites Work
- Graph searching and a min-max theorem for tree-width
- Searching and pebbling
- Directed tree-width
- Directed path-width and monotonicity in digraph searching
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Introducing directed tree width
- Complexity of Finding Embeddings in a k-Tree
- Title not available (Why is that?)
- Title not available (Why is that?)
- Mathematical Foundations of Computer Science 2005
- Logic for Programming, Artificial Intelligence, and Reasoning
- Digraph measures: Kelly decompositions, games, and orderings
- Alternation
- Results on the propositional \(\mu\)-calculus
- Fugitive-search games on graphs and related parameters
- Directed tree-width examples
- Digraph Decompositions and Monotonicity in Digraph Searching
- On model checking for the \(\mu\)-calculus and its fragments
- Graph minors. III. Planar tree-width
- DAG-Width and Parity Games
- Fast mu-calculus model checking when tree-width is bounded.
- DAG-width
- Clique-Width and Parity Games
- Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
Cited In (43)
- Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
- Directed NLC-width
- An algorithmic metatheorem for directed treewidth
- Computing the zig-zag number of directed graphs
- Directed path-decompositions
- Are there any good digraph width measures?
- Width-restricted layering of acyclic digraphs with consideration of dummy nodes
- DAG-width and circumference of digraphs
- Congestion-free rerouting of flows on DAGs
- The localization game on oriented graphs
- On directed covering and domination problems
- Redicolouring digraphs: directed treewidth and cycle-degeneracy
- On directed covering and domination problems
- On the complexity of directed intersection representation of DAGs
- On the hardness of finding near-optimal multicuts in directed acyclic graphs
- On the monotonicity of process number
- Directed width parameters and circumference of digraphs
- Directed tree-width
- Spined categories: generalizing tree-width beyond graphs
- Graph searching games and width measures for directed graphs
- Entanglement and the complexity of directed graphs
- Title not available (Why is that?)
- Digraph coloring and distance to acyclicity
- On the structure of solution-sets to regular word equations
- On width measures and topological problems on semi-complete digraphs
- Directed width parameters on semicomplete digraphs
- Digraph width measures in parameterized algorithmics
- Directed elimination games
- Approximation algorithms for digraph width parameters
- The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs
- DAG-width is PSPACE-complete
- Jumping robbers in digraphs
- Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth
- DAG-Width and Parity Games
- A linear-time parameterized algorithm for computing the width of a DAG
- Digraph decompositions and monotonicity in digraph searching
- How to compute digraph width measures on directed co-graphs
- Parameterized Algorithms for Parity Games
- Forbidden directed minors and Kelly-width
- The complexity of optimizing atomic congestion
- Directed tree-width examples
- Digraphs of bounded width
- Digraphs of bounded elimination width
This page was built for publication: The dag-width of directed graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q444380)
