DAG-Width and Parity Games

DOI10.1007/11672142_43zbMath1136.68447OpenAlexW1487444734WikidataQ58215648 ScholiaQ58215648MaRDI QIDQ5449827

Dietmar Berwanger, Paul Hunter, Anuj Dawar, Stephan Kreutzer

Publication date: 19 March 2008

Published in: STACS 2006 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11672142_43

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Games involving graphs (91A43) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20)

Related Items

Symmetric Strategy Improvement ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Digraph Decompositions and Monotonicity in Digraph Searching ⋮ From Parity and Payoff Games to Linear Programming ⋮ Directed width parameters on semicomplete digraphs ⋮ Solving parity games in big steps ⋮ Jumping robbers in digraphs ⋮ Alternating traps in Muller and parity games ⋮ Entanglement and the complexity of directed graphs ⋮ Are there any good digraph width measures? ⋮ The Rabin index of parity games: its complexity and approximation ⋮ Monotonicity of Non-deterministic Graph Searching ⋮ Characterization and Recognition of Digraphs of Bounded Kelly-width ⋮ Monotonicity of strong searching on digraphs ⋮ Synthesising Strategy Improvement and Recursive Algorithms for Solving 2.5 Player Parity Games ⋮ Graph operations on parity games and polynomial-time algorithms ⋮ Finite Automata, Digraph Connectivity, and Regular Expression Size ⋮ Digraph decompositions and monotonicity in digraph searching ⋮ Unnamed Item ⋮ The dag-width of directed graphs ⋮ Digraphs of bounded elimination width ⋮ Parity games on undirected graphs ⋮ How to compute digraph width measures on directed co-graphs ⋮ The Descriptive Complexity of Parity Games ⋮ Monotonicity of non-deterministic graph searching ⋮ Digraph measures: Kelly decompositions, games, and orderings ⋮ An annotated bibliography on guaranteed graph searching ⋮ Finding a subdivision of a digraph ⋮ Approximation algorithms for digraph width parameters ⋮ Digraph searching, directed vertex separation and directed pathwidth ⋮ Forbidden directed minors and Kelly-width ⋮ Solving parity games via priority promotion ⋮ New deterministic algorithms for solving parity games ⋮ First-cycle games ⋮ Minimal equivalent subgraphs containing a given set of arcs ⋮ An extended tree-width notion for directed graphs related to the computation of permanents ⋮ Towards fixed-parameter tractable algorithms for abstract argumentation ⋮ On complexity of minimum leaf out-branching problem ⋮ Recognizing digraphs of Kelly-width 2 ⋮ Bounded treewidth as a key to tractability of knowledge representation and reasoning ⋮ LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Are There Any Good Digraph Width Measures? ⋮ Directed width parameters and circumference of digraphs ⋮ The Complexity of Nash Equilibria in Infinite Multiplayer Games ⋮ Solving Parity Games in Big Steps ⋮ Undirected Graphs of Entanglement 2 ⋮ LIFO-Search on Digraphs: A Searching Game for Cycle-Rank ⋮ Polynomial-Time Under-Approximation of Winning Regions in Parity Games ⋮ A Polynomial Time Algorithm for Bounded Directed Pathwidth ⋮ On Digraph Width Measures in Parameterized Algorithmics ⋮ Digraphs of Bounded Width ⋮ Unnamed Item ⋮ Complexity of node coverage games