Entanglement and the complexity of directed graphs
From MaRDI portal
Publication:1929212
DOI10.1016/j.tcs.2012.07.010zbMath1256.05086MaRDI QIDQ1929212
Erich Grädel, Roman Rabinovich, Dietmar Berwanger, Łukasz Kaiser
Publication date: 7 January 2013
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.07.010
parity games; treewidth; graph searching games; DAG-width; structural graph theory; digraph algorithms; Kelly-width
91A43: Games involving graphs
05C85: Graph algorithms (graph-theoretic aspects)
05C20: Directed graphs (digraphs), tournaments
91A24: Positional games (pursuit and evasion, etc.)
05C57: Games on graphs (graph-theoretic aspects)
Related Items
An algorithmic metatheorem for directed treewidth, The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs, Parameterized Algorithms for Parity Games
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The dag-width of directed graphs
- Graph minors. III. Planar tree-width
- Results on the propositional \(\mu\)-calculus
- Digraph measures: Kelly decompositions, games, and orderings
- Graph minors. I. Excluding a forest
- Space-bounded reducibility among combinatorial problems
- A partial k-arboretum of graphs with bounded treewidth
- Infinite games on finitely coloured graphs with applications to automata on infinite trees
- Graph searching and a min-max theorem for tree-width
- Directed tree-width
- Transition graphs and the star-height of regular events
- The variable hierarchy of the \(\mu\)-calculus is strict
- Directed Graphs of Entanglement Two
- The Descriptive Complexity of Parity Games
- DAG-width
- Alternation
- Bisimulation, modal logic and model checking games
- Digraph Decompositions and Monotonicity in Digraph Searching
- DAG-Width and Parity Games
- Undirected Graphs of Entanglement 2
- Logic for Programming, Artificial Intelligence, and Reasoning
- Computer Aided Verification
