Entanglement and the complexity of directed graphs

DOI10.1016/j.tcs.2012.07.010zbMath1256.05086MaRDI 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 games; treewidth; graph searching games; DAG-width; structural graph theory; digraph algorithms; Kelly-width

Mathematics Subject Classification ID

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

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

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