A deterministic distributed algorithm for exact weighted all-pairs shortest paths in O(n^3/2) rounds

DOI10.1145/3212734.3212773MaRDI QIDQ5197684zbMATH OpenOpenAlexWikidataFDO

Authors Udit Agarwal, Vijaya Ramachandran, Valerie King, Matteo Pontecorvi

Publication date 19 September 2019

Published in Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1804.05441

zbMATH Keywords

blocker setCongest modeldistributed algorithmsshortest paths

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Abstract: We present a deterministic distributed algorithm to compute all-pairs shortest paths(APSP) in an edge-weighted directed or undirected graph. Our algorithm runs in $ildeO(n^{3/2})$ rounds in the Congest model, where $n$ is the number of nodes in the graph. This is the first $o(n^2)$ rounds deterministic distributed algorithm for the weighted APSP problem. Our algorithm is fairly simple and incorporates a deterministic distributed algorithm we develop for computing a `blocker set' cite{King99}, which has been used earlier in sequential dynamic computation of APSP.

Recommendations

• Distributed exact weighted all-pairs shortest paths in near-linear time
• Distributed approximation algorithms for weighted shortest paths
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• More Algorithms for All-Pairs Shortest Paths in Weighted Graphs

Cited in

(12)

• Fast approximate shortest paths in the congested clique
• Single-source shortest paths in the CONGEST model with improved bounds
• The sparsest additive spanner via multiple weighted BFS trees
• Optimal distributed all pairs shortest paths and applications
• Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
• The Sparsest Additive Spanner via Multiple Weighted BFS Trees
• Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles
• Quantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model
• Distributed exact weighted all-pairs shortest paths in near-linear time
• Quadratic and near-quadratic lower bounds for the CONGEST model
• Distributed distance approximation
• Distance computations in the hybrid network model via oracle simulations

This page was built for publication: A deterministic distributed algorithm for exact weighted all-pairs shortest paths in \(\tilde{O}(n^{3/2})\) rounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5197684)