A Deterministic Distributed Algorithm for Weighted All Pairs Shortest Paths Through Pipelining

• DOI: 10.48550/arxiv.1807.08824
• Publication Date: 2018-01-01
• Authors: Udit Agarwal; Vijaya Ramachandran
• Keywords: FOS: Computer and information sciences; Computer Science - Distributed, Parallel, and Cluster Computing; Computer Science - Data Structures and Algorithms; Data Structures and Algorithms (cs.DS); 0102 computer and information sciences; Distributed, Parallel, and Cluster Computing (cs.DC); 01 natural sciences

We present a new pipelined approach to compute all pairs shortest paths (APSP) in directed graph with nonnegative integer edge weights (including zero weights) the CONGEST model distributed setting. Our deterministic algorithm computes of distance at most $Δ$ for vertices $2 n \sqrtΔ + 2n$ rounds, and more generally, it h-hop k sources $2\sqrt{nkh} k$ rounds. The is simple, has some novel features nontrivial analysis.It uses only edges communication. This can be used as base within asymptotically faster algorithms that match or improve on current best bound $\tilde{O}(n^{3/2})$ rounds this problem when are $O(n)$ path distances $\tilde{O}(n^{3/2})$.