The dag-width of directed graphs

DOI10.1016/j.jctb.2012.04.004zbMath1246.05065OpenAlexW2127618440WikidataQ58215516 ScholiaQ58215516MaRDI QIDQ444380

Anuj Dawar, Paul Hunter, Dietmar Berwanger, Jan Obdržálek, Stephan Kreutzer

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

zbMATH Keywords

parity gamesgraph searching gamesstructural graph theorydigraph algorithmsdirected graph decompositions

Mathematics Subject Classification ID

Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (30)

An algorithmic metatheorem for directed treewidth ⋮ Computing the zig-zag number of directed graphs ⋮ On the monotonicity of process number ⋮ Directed width parameters on semicomplete digraphs ⋮ Jumping robbers in digraphs ⋮ DAG-width is PSPACE-complete ⋮ Congestion-Free Rerouting of Flows on DAGs ⋮ Parameterized Algorithms for Parity Games ⋮ Beyond bidimensionality: parameterized subexponential algorithms on directed graphs ⋮ Entanglement and the complexity of directed graphs ⋮ Spined categories: generalizing tree-width beyond graphs ⋮ Are there any good digraph width measures? ⋮ Directed elimination games ⋮ The localization game on oriented graphs ⋮ Directed NLC-width ⋮ Digraphs of bounded elimination width ⋮ Digraph width measures in parameterized algorithmics ⋮ How to compute digraph width measures on directed co-graphs ⋮ Approximation algorithms for digraph width parameters ⋮ The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs ⋮ On directed covering and domination problems ⋮ Forbidden directed minors and Kelly-width ⋮ On the hardness of finding near-optimal multicuts in directed acyclic graphs ⋮ Directed width parameters and circumference of digraphs ⋮ DAG-Width and Circumference of Digraphs ⋮ Directed Path-Decompositions ⋮ On width measures and topological problems on semi-complete digraphs ⋮ Digraphs of Bounded Width ⋮ On Directed Covering and Domination Problems ⋮ Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. III. Planar tree-width
• Results on the propositional \(\mu\)-calculus
• Digraph measures: Kelly decompositions, games, and orderings
• Graph searching and a min-max theorem for tree-width
• Fugitive-search games on graphs and related parameters
• Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree 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
• Directed tree-width examples
• DAG-width
• Clique-Width and Parity Games
• Complexity of Finding Embeddings in a k-Tree
• Alternation
• Digraph Decompositions and Monotonicity in Digraph Searching
• DAG-Width and Parity Games
• Mathematical Foundations of Computer Science 2005
• Logic for Programming, Artificial Intelligence, and Reasoning
• Computer Aided Verification
• On model checking for the \(\mu\)-calculus and its fragments

This page was built for publication: The dag-width of directed graphs