Parallel Approximate Shortest Paths using Low Diameter Graph Decomposition
Shen Chen Xu
September 25, 2013
Efficiently scaling shortest path algorithms to multiple processors is one of the major open problems in parallel computing. Despite decades of progresses in theory and practice, obtaining speedups proportional to the number of processors over sequential algorithms remains a challenging problem. In this talk we give algorithms that compute (1+\epsilon)-approximate shortest paths in sub-linear time and nearly linear work.