Lehtinen, Karoliina, Parys, Paweł 
ORCID: 0000-0001-7247-1408, Schewe, Sven ORCID: 0000-0002-9093-9518 and Wojtczak, Dominik
(2022)
A Recursive Approach to Solving Parity Games in Quasipolynomial Time.
Logical Methods in Computer Science, Volume (1).
|
Text
2104.09717.pdf - Published version Download (1MB) | Preview |
Abstract
<jats:p>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 $n^{O\left(\log\left(1+\frac{d}{\log n}\right)\right)}$, for parity games of size $n$ with $d$ priorities, in line with previous quasipolynomial-time solutions.</jats:p>
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | 46 Information and Computing Sciences |
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 19 Nov 2021 08:16 |
| Last Modified: | 20 Jun 2024 20:24 |
| DOI: | 10.46298/lmcs-18(1:8)2022 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3143440 |
Altmetric
Altmetric
