Optimal distributed all pairs shortest paths and applications

DOI10.1145/2332432.2332504zbMath1301.68256OpenAlexW2048098617MaRDI QIDQ2933812

Roger Wattenhofer, Stephan Holzer

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

approximationlower boundgirtheccentricityradiusdistributed computingmessage passingall pairs shortest pathsperipheral vertices

Mathematics Subject Classification ID

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

Related Items (18)

Single-source shortest paths in the CONGEST model with improved bounds ⋮ Low-congestion shortcuts without embedding ⋮ Distributed Testing of Distance-k Colorings ⋮ Distributed distance computation and routing with small messages ⋮ The sparsest additive spanner via multiple weighted BFS trees ⋮ Distributed Graph Algorithms and their Complexity: An Introduction ⋮ Algebraic methods in the congested clique ⋮ Distributed construction of purely additive spanners ⋮ Unnamed Item ⋮ Fast distributed algorithms for testing graph properties ⋮ Approximate proof-labeling schemes ⋮ Efficient and Decentralized Polling Protocol for General Social Networks ⋮ The Sparsest Additive Spanner via Multiple Weighted BFS Trees ⋮ Fast approximate shortest paths in the congested clique ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Distributed Spanner Approximation ⋮ Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time ⋮ A distributed enumeration algorithm and applications to all pairs shortest paths, diameter\dots

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