ALCOMFT-TR-02-50

Ulrich Meyer
Buckets Strike Back: Improved Parallel Shortest-Paths
MPI. Work packages 1 and 2. May 2002.

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= O(log² n · min_i {2ⁱ · \mathbfE[ L] + |V_i| }) average-case time using 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ⁱ. 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. The algorithm allows adaptation to distributed memory machines, too.

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