Exponential examples of solving parity games

DOI10.1134/S0965542516040114zbMath1390.91075MaRDI QIDQ327255

Vasilij 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)

Cites Work

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

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