de.mpg.escidoc.pubman.appbase.FacesBean
English

# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

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

##### MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45038

Meyer,  Ulrich
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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