Rabin Games and Colourful Universal Trees

Rupak Majumdar, Irmak Saglam, K. S. Thejaswini

We provide an algorithm to solve Rabin and Streett games over graphs with $n$ vertices, $m$ edges, and $k$ colours that runs in $\tilde{O}\left(mn(k!{)}^{1+o(1)}\right)$ time and $O…