Literature for Summer School on Shortest Paths

Recommended literature for PATH05. Hardcopies of the references marked with an (*) will be made available for all participants.

Natashia Boland

R. K. Ahuja et al, Applications of network optimization, Handbook 7 in Operations Research and Management Science: Network Models (Chapter 1, Section 3), edited by M.O. Ball et al., 1995.

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

(*) Camil Demetrescu, Pino Italiano, Dynamic shortest paths and transitive closure: an annotated bibliography, manuscript. [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)]

Andrew Goldberg

(*) R. E. Tarjan, Shortest paths, Data Structures and Network Algorithms (Chapter 7), SIAM, 1983.

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.

Mikkel Thorup

Mikkel Thorup, Undirected single source shortest paths with positive integer weights in linear time, Journal of the ACM, 46, 362-394, 1999. (Preliminary version in FOCS'97.) [Link to journal article]

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.

Uri Zwick

Uri Zwick, All pairs shortest paths using bridging sets and rectangular matrix multiplication, Journal of the ACM, 49, 289--317 (2002). [Draft of journal version (ps)] [Link to journal article] [Slides of a talk (ps.gz)]

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.