A deterministic subexponential algorithm for solving parity games

DOI10.1145/1109557.1109571zbMath1192.91013OpenAlexW4244848635MaRDI QIDQ3581528

Uri Zwick, Marcin Jurdziński, Mike S. Paterson

Publication date: 16 August 2010

Published in: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.101.7326

Mathematics Subject Classification ID

Games involving graphs (91A43) Specification and verification (program logics, model checking, etc.) (68Q60) Software, source code, etc. for problems pertaining to game theory, economics, and finance (91-04)

Related Items (32)

Graph Games and Reactive Synthesis ⋮ Cooking Your Own Parity Game Preorders Through Matching Plays ⋮ Parity game reductions ⋮ On canonical forms for zero-sum stochastic mean payoff games ⋮ Alternating traps in Muller and parity games ⋮ Robust worst cases for parity games algorithms ⋮ A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions ⋮ A convex programming-based algorithm for mean payoff stochastic games with perfect information ⋮ A CSP-Based Approach for Solving Parity Game ⋮ A survey of stochastic \(\omega \)-regular games ⋮ Solving parity games by a reduction to SAT ⋮ Value Iteration ⋮ Graph operations on parity games and polynomial-time algorithms ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A superpolynomial lower bound for strategy iteration based on snare memorization ⋮ The Descriptive Complexity of Parity Games ⋮ On short paths interdiction problems: Total and node-wise limited interdiction ⋮ The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs ⋮ Inf-datalog, Modal Logic and Complexities ⋮ Cyclic games and linear programming ⋮ Concurrent reachability games ⋮ Solving parity games via priority promotion ⋮ A Multi-Core Solver for Parity Games ⋮ Unnamed Item ⋮ Meanings of Model Checking ⋮ Solving μ-Calculus Parity Games by Symbolic Planning ⋮ Solving Parity Games in Big Steps ⋮ Solving Parity Games in Practice ⋮ Recursive algorithm for parity games requires exponential time

This page was built for publication: A deterministic subexponential algorithm for solving parity games