4817
правок
Декрементный алгоритм нахождения кратчайших путей между всеми парами: различия между версиями
Перейти к навигации
Перейти к поиску
Декрементный алгоритм нахождения кратчайших путей между всеми парами (посмотреть исходный код)
Версия от 15:51, 20 апреля 2013
, 20 апреля 2013→Литература
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 50: | Строка 50: | ||
== Литература == | == Литература == | ||
1. Ahuja, R., Magnanti, T., Orlin, J.: Network Flows: Theory, Algorithms and Applications. Prentice Hall, Englewood Cliffs, NJ (1993) | 1. Ahuja, R., Magnanti, T., Orlin, J.: Network Flows: Theory, Algorithms and Applications. Prentice Hall, Englewood Cliffs, NJ (1993) | ||
2. Demetrescu, C., Italiano, G.: A new approach to dynamic all pairs shortest paths. J. Assoc. Comp. Mach. 51,968-992 (2004) | 2. Demetrescu, C., Italiano, G.: A new approach to dynamic all pairs shortest paths. J. Assoc. Comp. Mach. 51,968-992 (2004) | ||
3. Dijkstra, E.: A note on two problems in connexion with graphs. Numerische Mathematik 1,269-271 (1959) | 3. Dijkstra, E.: A note on two problems in connexion with graphs. Numerische Mathematik 1,269-271 (1959) | ||
4. Even, S., Gazit, H.: Updating distances in dynamic graphs. Meth. Op. Res. 49, 371-387(1985) | 4. Even, S., Gazit, H.: Updating distances in dynamic graphs. Meth. Op. Res. 49, 371-387(1985) | ||
5. Fredman, M., Tarjan, R.: Fibonacci heaps and their use in improved network optimization algorithms. J. ACM 34, 596-615 (1987) | 5. Fredman, M., Tarjan, R.: Fibonacci heaps and their use in improved network optimization algorithms. J. ACM 34, 596-615 (1987) | ||
6. Fredman, M.L.: New bounds on the complexity of the shortest path problems. SIAM J. Comp. 5(1), 87-89 (1976) | 6. Fredman, M.L.: New bounds on the complexity of the shortest path problems. SIAM J. Comp. 5(1), 87-89 (1976) | ||
7. Frigioni, D., Marchetti-Spaccamela,A., Nanni, U.: Semi-dynamic algorithms for maintaining single source shortest paths trees. Algorithmica 22, 250-274 (1998) | 7. Frigioni, D., Marchetti-Spaccamela,A., Nanni, U.: Semi-dynamic algorithms for maintaining single source shortest paths trees. Algorithmica 22, 250-274 (1998) | ||
8. Frigioni, D., Marchetti-Spaccamela, A., Nanni, U.: Fully dynamic algorithms for maintaining shortest paths trees. J. Algorithm 34,351-381 (2000) | 8. Frigioni, D., Marchetti-Spaccamela, A., Nanni, U.: Fully dynamic algorithms for maintaining shortest paths trees. J. Algorithm 34,351-381 (2000) | ||
9. King, V.: Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In: Proc. 40th IEEE Symposium on Foundations of Computer Science (FOCS'99), pp. 81-99. IEEE Computer Society, New York, USA (1999) | 9. King, V.: Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In: Proc. 40th IEEE Symposium on Foundations of Computer Science (FOCS'99), pp. 81-99. IEEE Computer Society, New York, USA (1999) | ||
10. Knuth, D., Plass, M.: Breaking paragraphs into lines. Software-Practice Exp. 11,1119-1184 (1981) | 10. Knuth, D., Plass, M.: Breaking paragraphs into lines. Software-Practice Exp. 11,1119-1184 (1981) | ||
11. Loubal, P.: A network evaluation procedure. Highway Res. Rec. 205,96-109(1967) | 11. Loubal, P.: A network evaluation procedure. Highway Res. Rec. 205,96-109(1967) | ||
12. Murchland, J.: The effect of increasing or decreasing the length of a single arc on all shortest distances in a graph, tech. rep., LBS-TNT-26, London Business School. Transport Network The ory Unit, London, UK (1967) | 12. Murchland, J.: The effect of increasing or decreasing the length of a single arc on all shortest distances in a graph, tech. rep., LBS-TNT-26, London Business School. Transport Network The ory Unit, London, UK (1967) | ||
13. Pettie, S.: A new approach to all-pairs shortest paths on real-weighted graphs. Theor. Comp. Sci. 312,47-74 (2003) special issue of selected papers from ICALP (2002) | 13. Pettie, S.: A new approach to all-pairs shortest paths on real-weighted graphs. Theor. Comp. Sci. 312,47-74 (2003) special issue of selected papers from ICALP (2002) | ||
14. Ramalingam, G.: Bounded incremental computation. Lect. Note Comp. Sci. 1089 (1996) | 14. Ramalingam, G.: Bounded incremental computation. Lect. Note Comp. Sci. 1089 (1996) | ||
15. Ramalingam, G., Reps, T.: An incremental algorithm for a generalization of the shortest path problem. J. Algorithm 21, 267-305(1996) | 15. Ramalingam, G., Reps, T.: An incremental algorithm for a generalization of the shortest path problem. J. Algorithm 21, 267-305(1996) | ||
16. Ramalingam, G., Reps, T.: On the computational complexity of dynamic graph problems. Theor. Comp. Sci. 158, 233-277 (1996) | 16. Ramalingam, G., Reps, T.: On the computational complexity of dynamic graph problems. Theor. Comp. Sci. 158, 233-277 (1996) | ||
17. Rodionov, V.: The parametric problem of shortest distances. USSR Comp. Math. Math. Phys. 8, 336-343 (1968) | 17. Rodionov, V.: The parametric problem of shortest distances. USSR Comp. Math. Math. Phys. 8, 336-343 (1968) | ||
18. Schulz, F., Wagner, D., Weihe, K.: Dijkstra's algorithm on-line: an empirical case study from public railroad transport. In: Proc. 3rd Workshop on Algorithm Engineering (WAE'99), pp. 110-123. Notes in Computer Science 1668. London, UK (1999) | 18. Schulz, F., Wagner, D., Weihe, K.: Dijkstra's algorithm on-line: an empirical case study from public railroad transport. In: Proc. 3rd Workshop on Algorithm Engineering (WAE'99), pp. 110-123. Notes in Computer Science 1668. London, UK (1999) | ||
19. Takaoka, T.: A new upper bound on the complexity of the all-pairs shortest path problem. Inf. Proc. Lett. 43,195-199 (1992) | 19. Takaoka, T.: A new upper bound on the complexity of the all-pairs shortest path problem. Inf. Proc. Lett. 43,195-199 (1992) | ||