Optimal distributed all pairs shortest paths and applications

DOI10.1145/2332432.2332504MaRDI QIDQ2933812zbMATH OpenOpenAlexFDO

Authors Stephan Holzer, Roger Wattenhofer

Publication date 5 December 2014

Published in Proceedings of the 2012 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2332432.2332504

zbMATH Keywords

distributed computingapproximationlower boundeccentricitygirthradiusall pairs shortest pathsmessage passingperipheral vertices

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15) Distributed systems (68M14)

Recommendations

• scientific article; zbMATH DE number 1304097
• A deterministic distributed algorithm for exact weighted all-pairs shortest paths in \(\tilde{O}(n^{3/2})\) rounds
• Distributed approximation algorithms for weighted shortest paths
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)

Cited in

(26)

• Approximate proof-labeling schemes
• Networks cannot compute their diameter in sublinear time
• Distributed algorithms for network diameter and girth
• Sharing information for the all pairs shortest path problem
• Distributed spanner approximation
• scientific article; zbMATH DE number 7559158 (Why is no real title available?)
• OFDP: a distributed algorithm for finding disjoint paths with minimum total length in wireless sensor networks
• Distributed graph algorithms and their complexity: an introduction
• Near-optimal approximate shortest paths and transshipment in distributed and streaming models
• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• Distributed exact weighted all-pairs shortest paths in near-linear time
• Efficient distributed computation of distance sketches in networks
• Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
• Low-congestion shortcuts without embedding
• Distributed Testing of Distance-k Colorings
• Distributed distance computation and routing with small messages
• Fast distributed algorithms for girth, cycles and small subgraphs
• The Sparsest Additive Spanner via Multiple Weighted BFS Trees
• Fast approximate shortest paths in the congested clique
• A distributed enumeration algorithm and applications to all pairs shortest paths, diameter\dots
• scientific article; zbMATH DE number 1304097 (Why is no real title available?)
• Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
• Improved hardness of approximation of diameter in the CONGEST model
• The sparsest additive spanner via multiple weighted BFS trees
• Efficient and decentralized polling protocol for general social networks
• Single-source shortest paths in the CONGEST model with improved bounds

This page was built for publication: Optimal distributed all pairs shortest paths and applications

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