Tech Report CS-95-04
Parallel and Dynamic Shortest-Path Algorithms for Sparse Graphs
Sairam Subramanian
May 1995
Abstract:
Computing single-source shortest paths is a fundamental and ubiquitous problem in network analysis. Aside from the importance of this problem in its own right, often the problem arises in the solution of other optimization problems like network flow and matching.
In this thesis we consider the problem of computing shortest paths in parallel, dynamic, and sequential realms. We also consider the related problem of graph-reachability in these settings.
(complete text in pdf or gzipped postscript)