Literature for Summer School on Shortest Paths (PATH05)
Literature for Summer School on Shortest Paths J. Desrosiers et al, Time constrained routing and scheduling, Handbook 8 in Operations Research and Management Science: Network Routing, edited by M.O. Ball et al., 1995.
R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Network flows: theory, algorithms, and applications (Chapter 4.2), Prentice Hall, New Jersey, 1993.
(*) Natashia Boland, Irina Dumitrescu, Improved preprocessing, labeling and scaling algorithms for the weight-constrained shortest path problem, Networks 42, 135-153, 2003. [Link to journal article]
Natashia Boland, John Dethridge, Irina Dumitrescu, Accelerated label setting algorithms for the elementary resource constrained shortest path problem, Operations Research Letters, to appear. [Draft (pdf)]
Camil Demetrescu and Pino Italiano, Dynamic graphs, Handbook on Data Structures and Applications, Chapter 36. Dinesh Mehta and Sartaj Sahni (eds.), CRC Press Series, in Computer and Information Science, January 2005. [Draft (pdf)]
A. V. Goldberg, Scaling algorithms for the shortest paths problem, SIAM Journal on Computing, 24, 494-504, 1995. [Draft of journal version], [Link to proceedings version]
B. V. Cherkassky, A. V. Goldberg, Negative-cycle detection algorithms, Mathematical Programming, 85, 277-311, 1999. [Link to journal article]
E. V. Denardo, B. L. Fox, Shortest-route methods: 1. Reaching, pruning, and buckets, Operations Research 27, 161-186. 1979.
A. V. Goldberg, A practical shortest path algorithm with linear expected time, submitted for publication. [Draft (ps)]
I. Pohl, Bi-directional search, Machine Intelligence 6, Edinburgh Univ. Press, 124-140, 1971.
P. E. Hart, N. J. Nilsson, B. Raphael, A formal basis for the heuristic determination of minimum cost paths, IEEE Transactions on System Science and Cybernetics SSC-4, number 2, 1968.
Yijie Han, Mikkel Thorup, Integer sorting in 0(n sqrt (log log n)) expected time and linear space, Proceedings of the 43nd IEEE Symposium on Foundations of Computer Science (FOCS)}, 135-144, 2002. [Link to journal article]
Mikkel Thorup, Integer priority queues with decrease key in constant time and the single source shortest paths problem, J. Comp. Syst. Sc., 69, 330-353, 2004. (Preliminary version in STOC'03.) [Link to proceedings version]
Bernard Fortz, Jennifer Rexford, Mikkel Thorup, Traffic engineering with traditional IP routing protocols, IEEE Communications Magazine, 40, 118--124, 2002. [Link to preliminary version (pdf).]
Bernard Fortz, Mikkel Thorup, Increasing Internet capacity using local search, Computational Optimization and Applications, 29, 13-48, 2004. (Preliminary version in INFOCOM'00.) [Link to journal article]
Comments: The first three papers are on asymptotic SSSP algorithms in directed and undirected graphs with integer weights, while the two last papers are on dynamic shortest paths in Internet optimization.
Mikkel Thorup, Uri Zwick, Approximate distance oracles, Journal of the ACM, 52, 1-24 (2005). (Preliminary version in Proc. of 33rd STOC (2001), 183-192.) [Draft of proceedings version (ps.gz)] [Link to proceedings version] [Draft of journal version (ps)] [Link to journal article] [Presentation (ppt)]
Last Update: June 21, 2005 by Martin Zachariasen.