de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

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.