The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs

Felix Canavoi, Erich Grädel, Roman Rabinovich

For some time the discrete strategy improvement algorithm due to Jurdzinski and Voge had been considered as a candidate for solving parity games in polynomial time. However, it has…