# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Buckets Strike Back: Improved Parallel Shortest-Paths

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Meyer, U. (2002). Buckets Strike Back: Improved Parallel Shortest-Paths. In *International
Parallel and Distributed Processing Symposium (IPDPS-02)* (pp. 75-75). Los Alamitos, USA: IEEE.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-2F2B-9

##### 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.