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.