|
|
|
|
Литература
|
|
| |
| 1. |
Henrik Björklund, Sven Sandberg, and Sergei Vorobyov, “Memoryless determinacy of parity and mean payoff games: a simple proof”, Theoretical Computer Science, 310 (2004), 365–378    |
| 2. |
Henrik Björklund, Sven Sandberg, and Sergei Vorobyov, A combinatorial strongly subexponential strategy improvement
algorithm for mean payoff games, DIMACS Technical Report № 5, 2004 |
| 3. |
Y. J. Chu and T. H. Liu, “On the shortest arborescence of a directed graph”, Science Sinica, 14 (1965), 1396–1400 |
| 4. |
A. Ehrenfeucht and J. Mycielski, “Positional strategies for mean payoff games”, International Journal of Game Theory, 8 (1979), 109–113 |
| 5. |
V. A. Gurvich, A. V. Karzanov, and L. G. Khachiyan, “Cyclic games and an algorithm to find minimax cycle means in directed
graphs”, USSR Computational Mathematics and Mathematical Physics, 28 (1988), 85–91  |
| 6. |
T. Gallai, “Maximum-Minimum Sätze über Graphen”, Acta Mathematica Academiae Scientiarum Hungaricae, 9 (1958), 395–434 |
| 7. |
Alexander Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer-Verlag, Berlin, 2003 |
| 8. |
Donald B. Johnson, “Efficient algorithms for shortest paths in sparse networks”, Journal of the ACM, 24 (1977), 1–13 |
| 9. |
Marcin Jurdziński, “Small progress measures for solving parity games”, Proceedings of 17th Annual Symposium on Theoretical Aspects of
Computer Science, Lecture Notes in Computer Science, 1770, eds. Hotst Reichel and Sophie Tison, Springer, 2000, 290–301  |
| 10. |
Marcin Jurdziński, Mike Paterson, and Uri Zwick, “A Deterministic Subexponential Algorithm for Solving Parity Games” (to appear) |
| 11. |
Hartmut Klauck, “Algorithms for Parity Games”, Automata, Logics, and Infinite Games, Lecture Notes in Computer Science, 2500, eds. E. Grädel et al., Springer-Verlag, 2002, 107–129 |
| 12. |
Dexter Kozen, “Results on the propositional $\mu$-calculus”, Theoretical Computer Science, 27 (1983), 333–354 |
| 13. |
H. W. Kuhn, “The hungarian method for the assignment problem”, Naval Research Logistics Quarterly, 2 (1955), 83–97 |
| 14. |
Stephen Kwek and Kurt Mehlhorn, “Optimal Search for Rationals”, Information Processing Letters, 86 (2003), 23–26 |
| 15. |
N. Pisaruk, “Mean cost cyclical games”, Mathematics of Operations Research, 24 (1999), 817–828 |
| 16. |
Uri Zwick and Mike Paterson, “The complexity of mean payoff games on graphs”, Theoretical Computer Science, 158 (1996), 343–359 |
