@TechReport{ it:2002-026,
author = {Henrik Bj{\"o}rklund and Sven Sandberg and Sergei
Vorobyov},
title = {A Discrete Subexponential Algorithm for Parity Games},
institution = {Department of Information Technology, Uppsala University},
department = {Computing Science Division},
year = {2002},
number = {2002-026},
month = sep,
abstract = { We suggest a new randomized algorithm for solving Parity
Games with the worst case time complexity roughly
\[\min\left(O\left( n^3 \cdot \left( \frac{n}{k}+1
\right)^k \right), \;2^{O(\sqrt{n\log n})}\right),\] where
$n$ is the number of vertices and $k$ the number of colors
of the game. Comparable with the previously known
algorithms, which are efficient when the number of colors
is small, it is subexponential when the number of colors is
large, $k = \Omega(n^{1/2 + \varepsilon})$. }
}