Tech Report CS-95-04

Parallel and Dynamic Shortest-Path Algorithms for Sparse Graphs

Sairam Subramanian

May 1995


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)