16 references, page 1 of 2 [1] H. Bjo¨ rklund, S. Sandberg, and S. Vorobyov. A discrete subexponential algorithm for parity games. In Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, volume 2607 of LNCS, pages 663-674, London, UK, 2003. Springer-Verlag.

[2] H. Bjo¨ rklund and S. Vorobyov. A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games. Discrete Applied Mathematics, 155(2):210-229, 2007.

[3] A. Condon. On algorithms for simple stochastic games. In J.-Y. Cai, editor, Advances in Computational Complexity Theory, volume 13 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 51-73. American Mathematical Society, 1993.

[4] E. A. Emerson, C. S. Jutla, and A. P. Sistla. On model-checking for fragments of μ -calculus. In C. Courcoubetis, editor, Computer Aided Verification, 5th International Conference, CAV'93, volume 697 of LNCS, pages 385-396. Springer-Verlag, 1993.

[5] O. Friedman. A super-polynomial lower bound for the parity game strategy improvement algorithm as we know it. In Logic in Computer Science (LICS). IEEE, 2009.

[6] O. Friedman. A super-polynomial lower bound for the parity game strategy improvement algorithm as we know it. Preprint, January 2009.

[7] R. Howard. Dynamic Programming and Markov Processes. Technology Press and Wiley, 1960.

[8] M. Jurdzin´ ski, M. Paterson, and U. Zwick. A deterministic subexponential algorithm for solving parity games. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, pages 117-123. ACM/SIAM, 2006.

[9] L. Khachiyan, V. Gurvich, and J. Zhao. Extending dijkstra's algorithm to maximize the shortest path by node-wise limited arc interdiction. In Computer Science - Theory and Applications, volume 3967 of LNCS, pages 221-234. Springer, 2006.

[10] T. M. Liggett and S. A. Lippman. Stochastic games with perfect information and time average payoff. SIAM Review, 11(4):604-607, 1969.