Improving the complexity of Parys' recursive algorithm
classification
💻 cs.GT
cs.DS
keywords
algorithmcomplexityparysrecursiveboundsbriefbroadlycolours
read the original 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.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
Equilibria in Multiplayer Graph Games: An Algorithmic Study
Provides complexity results for the constrained existence problem of five equilibrium notions in multiplayer graph games.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.