Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time

DOI10.1137/20M1312782OpenAlexW3216768296MaRDI QIDQ5020729

Danupon Nanongkai, Aaron Bernstein

Publication date: 7 January 2022

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/20m1312782

zbMATH Keywords

graph algorithmsdistributed algorithmsCONGESTall-pairs shortest paths

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Cites Work

• Unnamed Item
• Unnamed Item
• Tight bounds for distributed minimum-weight spanning tree verification
• Near-linear lower bounds for distributed distance computations, even in sparse networks
• Further algebraic algorithms in the congested clique model and applications to graph-theoretic problems
• A fast distributed approximation algorithm for minimum spanning trees
• Algebraic methods in the congested clique
• Sparse matrix multiplication and triangle listing in the congested clique model
• A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
• Near-Optimal Scheduling of Distributed Algorithms
• Near-Optimal Distributed Maximum Flow
• Fast Partial Distance Estimation and Applications
• Distributed Minimum Cut Approximation
• Optimal distributed all pairs shortest paths and applications
• Distributed connectivity decomposition
• Can quantum communication speed up distributed computation?
• Distributed Algorithms for Network Diameter and Girth
• High-Probability Parallel Transitive-Closure Algorithms
• On a routing problem
• An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
• Approximate distance oracles
• Distributed Approximate Matching
• Efficient Algorithms for Shortest Paths in Sparse Networks
• Fast Distributed Construction of Smallk-Dominating Sets and Applications
• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
• Distributed Computing: A Locality-Sensitive Approach
• Distributed Verification and Hardness of Distributed Approximation
• Dense Subgraphs on Dynamic Networks
• A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees
• Distributed exact shortest paths in sublinear time
• Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
• Distributed Approximate Maximum Matching in the CONGEST Model.
• A Simple Deterministic Distributed MST Algorithm with Near-Optimal Time and Message Complexities
• Fast Approximate Shortest Paths in the Congested Clique
• Quantum Distributed Algorithm for the All-Pairs Shortest Path Problem in the CONGEST-CLIQUE Model
• Hardness of Distributed Optimization
• Efficient distributed source detection with limited bandwidth
• A Deterministic Distributed Algorithm for Exact Weighted All-Pairs Shortest Paths in Õ(n 3/2 ) Rounds
• Improved distributed algorithms for exact shortest paths
• Distributed approximation algorithms for weighted shortest paths
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• Fast routing table construction using small messages
• Almost-Tight Distributed Minimum Cut Algorithms

This page was built for publication: Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time