Zielonka's classic recursive algorithm for solving parity games is perhaps
the simplest among the many existing parity game algorithms. However, its
complexity is exponential, while currently the state-of-the-art algorithms have
quasipolynomial complexity. Here, we present a modification of Zielonka's
classic algorithm that brings its complexity down to
nO(log(1+dlogn)), for parity games of
size n with d priorities, in line with previous quasipolynomial-time
solutions.
Solving Parity Games in Theory and Practice; Funder: UK Research and Innovation; Code: EP/P020909/1
Foundations of Composition; Funder: European Commission; Code: 892704
Bibliographic References
5 Documents citing this article
Anne-Kathrin Schmuck;K. S. Thejaswini;Irmak Sağlam;Satya Prakash Nayak, Lecture notes in computer science, Solving Two-Player Games Under Progress Assumptions, pp. 208-231, 2023, 10.1007/978-3-031-50524-9_10.