Help Privacy Policy Disclaimer
  Advanced SearchBrowse




Conference Paper

Heaps are better than Buckets: Parallel Shortest Paths on Unbalanced Graphs


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

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available

Meyer, U. (2001). Heaps are better than Buckets: Parallel Shortest Paths on Unbalanced Graphs. In R. Sakellariou, J. Keane, J. Gurd, & L. Freeman (Eds.), Proceedings of the 7th International Euro-Par Conference on Parallel Processing (Euro-Par-01): (pp. 343-351). Berlin, Germany: Springer.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-3192-4
We propose a new parallel algorithm for the single-source shortest-path problem (SSSP). Its heap data structure is particularly advantageous on graphs with a moderate number of high degree nodes. On arbitrary directed graphs with $n$ nodes, $m$ edges and independent random edge weights uniformly distributed in the range $[0,1]$ and maximum shortest path weight $\Diam$ the PRAM version of our algorithm runs in ${\cal O}(\log^2 n \cdot \min_{i} \{2^i \cdot \Diam \cdot \log n+ |V_i| \})$ average-case time using ${\cal O}(n \cdot \log n +m )$ operations where $|V_i|$ is the number of graph vertices with degree at least $2^i$. For power-law graph models of the Internet or call graphs this results in the first work-efficient $o(n^{1/4})$ average-case time algorithm.