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)

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

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)

Cites Work

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

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)