Entanglement and the complexity of directed graphs

DOI10.1016/j.tcs.2012.07.010zbMath1256.05086OpenAlexW1977644778MaRDI QIDQ1929212

Łukasz Kaiser, Roman Rabinovich, Erich Grädel, Dietmar Berwanger

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

zbMATH Keywords

parity gamestreewidthgraph searching gamesDAG-widthstructural graph theorydigraph algorithmsKelly-width

Mathematics Subject Classification ID

Games involving graphs (91A43) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Positional games (pursuit and evasion, etc.) (91A24) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (13)

An algorithmic metatheorem for directed treewidth ⋮ Computing the zig-zag number of directed graphs ⋮ The mu-calculus and Model Checking ⋮ The \(\mu\)-calculus alternation depth hierarchy is infinite over finite planar graphs ⋮ Parameterized Algorithms for Parity Games ⋮ Drags: a compositional algebraic framework for graph rewriting ⋮ Spectral complexity of directed graphs and application to structural decomposition ⋮ Unnamed Item ⋮ The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs ⋮ Solving parity games via priority promotion ⋮ New deterministic algorithms for solving parity games ⋮ Unnamed Item ⋮ Digraphs of Bounded Width

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

This page was built for publication: Entanglement and the complexity of directed graphs