hide
Free keywords:
-
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.
