Item

Abstract

We propose a new parallel algorithm for the single-source shortest-path problem (SSSP). Its heap data structure is particularly advantageous on graphs with a moderate number of high degree nodes. On arbitrary directed graphs with $n$ nodes, $m$ edges and independent random edge weights uniformly distributed in the range $[0,1]$ and maximum shortest path weight $\Diam$ the PRAM version of our algorithm runs in ${\cal O}(\log^2 n \cdot \min_{i} \{2^i \cdot \Diam \cdot \log n+ |V_i| \})$ average-case time using ${\cal O}(n \cdot \log n +m )$ operations where $|V_i|$ is the number of graph vertices with degree at least $2^i$. For power-law graph models of the Internet or call graphs this results in the first work-efficient $o(n^{1/4})$ average-case time algorithm.