pith. sign in

arxiv: 1904.11810 · v4 · pith:OPS6Q6MZnew · submitted 2019-04-26 · 💻 cs.GT · cs.DS

Improving the complexity of Parys' recursive algorithm

classification 💻 cs.GT cs.DS
keywords algorithmcomplexityparysrecursiveboundsbriefbroadlycolours
0
0 comments X
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.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Equilibria in Multiplayer Graph Games: An Algorithmic Study

    cs.GT 2026-05 unverdicted novelty 5.0

    Provides complexity results for the constrained existence problem of five equilibrium notions in multiplayer graph games.