ALCOMFT-TR-01-94

Ulrich Meyer
Heaps are better than Buckets: Parallel Shortest Paths on unbalanced Graphs
MPI. Work packages 1 and 2. May 2001.

Abstract: 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 O(log² n · min_i {2ⁱ · \Diam · log n+ |V_i| }) average-case time using O(n · log n +m ) operations where |V_i| is the number of graph vertices with degree at least 2ⁱ. 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.

Postscript file: ALCOMFT-TR-01-94.ps.gz (94 kb).