A Faster Deterministic Distributed Algorithm for Weighted APSP Through Pipelining.
Udit Agarwal, Vijaya Ramachandran · arXiv (Cornell University) · 2018
We present a new approach to computing all pairs shortest paths (APSP) in a weighted directed graph in the Congest model in the distributed setting. Our approach gives a simple but nontrivial deterministic distributed APSP algorithm that runs in $\tilde{O}(n^{3/2})$ rounds. This bound matches a recent deterministic distributed algorithm in [ARKP18]. We then combine our new distributed APSP algorithm with a modified version of the algorithm in [ARKP18] to obtain an $\tilde{O}(n^{4/3})$ round deterministic distributed APSP algorithm in the Congest model, improving the previous best bound of $\tilde{O}(n^{3/2})$ rounds. We have a similar improvement in the bound for the problem of computing shortest path trees for k given sources. For this latter problem our deterministic distributed algorithm runs in $\tilde{O}(n \cdot k^{1/3})$ rounds. Our new approach in the $\tilde{O}(n^{3/2})$ round APSP algorithm is a pipelined strategy that computes each stage of Gabow's scaling algorithm in less than $2n^{3/2} + 2n$ rounds. While this algorithm has a simple description, it has some novel features and a nontrivial analysis.