Exponential examples of solving parity games

DOI10.1134/S0965542516040114zbMATH Open1390.91075MaRDI QIDQ327255FDOQ327255

Authors Vasiliĭ N. Lebedev 

Publication date 19 October 2016

Published in Computational Mathematics and Mathematical Physics (Search for Journal in Brave)

zbMATH Keywords

computational complexitycyclic gamedeciding the winner in cyclic gamespotential transformations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Games involving graphs (91A43)

Recommendations

• Recursive algorithm for parity games requires exponential time
• A Deterministic Subexponential Algorithm for Solving Parity Games
• Algorithms for solving parity games
• A brief excursion to parity games
• Effectively solvable classes of cyclical games

Cites work

• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• Cyclical games with prohibitions
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Mean cost cyclical games

Cited in

(3)

• The Stevens-Stirling-algorithm for solving parity games locally requires exponential time
• Effectively solvable classes of cyclical games
• Estimation of the complexity of the potential transformation algorithm for solving cyclic games on graphs

This page was built for publication: Exponential examples of solving parity games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q327255)