Item

Abstract

We study the average-case complexity of the parallel single-source shortest-path (SSSP) problem, assuming arbitrary directed graphs with $n$ nodes, $m$ edges, and independent random edge weights uniformly distributed in $[0,1]$. We provide a new bucket-based parallel SSSP algorithm that runs in $T={\cal O}(\log^2 n \cdot \min_{i} \{2^i \cdot \Diam + |V_i| \})$ average-case time using ${\cal O}(n +m+T)$ work on a PRAM where $\Diam$ denotes the maximum shortest-path weight and $|V_i|$ is the number of graph vertices with in-degree at least $2^i$. All previous algorithms either required more time or more work. The minimum performance gain is a logarithmic factor improvement; on certain graph classes, accelerations by factors of more than $n^{0.4}$ can be achieved.