Parallel approximate undirected shortest paths via low hop emulators
Alexandr Andoni, Clifford Stein, Peilin Zhong
Abstract
We present a (1+ε)-approximate parallel algorithm for computing shortest paths in undirected graphs, achieving poly(logn) depth and m poly(logn) work for n-nodes m-edges graphs. Although sequential algorithms with (nearly) optimal running time have been known for several decades, near-optimal parallel algorithms have turned out to be a much tougher challenge. For (1+ε)-approximation, all prior algorithms with poly(logn) depth perform at least Ω(mn c ) work for some constant c>0. Improving this long-standing upper bound obtained by Cohen (STOC’94) has been open for 25 years.
Topics & Concepts
CombinatoricsRunning timeUndirected graphComputer scienceApproximation algorithmUpper and lower boundsParallel algorithmMathematicsDiscrete mathematicsAlgorithmGraphMathematical analysisComplexity and Algorithms in GraphsComputational Geometry and Mesh GenerationOptimization and Search Problems