Improving the complexity of Parys' recursive algorithm


Lehtinen, Karoliina ORCID: 0000-0003-1171-8790, Schewe, Sven ORCID: 0000-0002-9093-9518 and Wojtczak, Dominik (2019) Improving the complexity of Parys' recursive algorithm. [Internet Publication]

[thumbnail of 1904.11810v4.pdf] Text
1904.11810v4.pdf - Published version
Download (131kB) | Preview

Abstract

Parys has recently proposed a quasi-polynomial version of Zielonka's recursive algorithm for solving parity games. In this brief note we suggest a variation of his algorithm that improves the complexity to meet the state-of-the-art complexity of broadly $2^{O((\log n)(\log c))}$, while providing polynomial bounds when the number of colours is logarithmic.

Item Type: Internet Publication
Uncontrolled Keywords: cs.GT, cs.GT, cs.DS
Depositing User: Symplectic Admin
Date Deposited: 12 Mar 2020 10:45
Last Modified: 18 Jan 2023 23:58
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3078737
Share
CORE (COnnecting REpositories)