Optimal distributed all pairs shortest paths and applications
DOI10.1145/2332432.2332504zbMATH Open1301.68256OpenAlexW2048098617MaRDI QIDQ2933812FDOQ2933812
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
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)
- Distributed exact shortest paths in sublinear time
distributed computingapproximationlower boundeccentricitygirthradiusall pairs shortest pathsmessage passingperipheral vertices
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)
Cited In (26)
- Sharing information for the all pairs shortest path problem
- A distributed enumeration algorithm and applications to all pairs shortest paths, diameter\dots
- Approximate proof-labeling schemes
- Fast distributed algorithms for testing graph properties
- Title not available (Why is that?)
- Distributed Testing of Distance-k Colorings
- Distributed construction of purely additive spanners
- Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
- OFDP: a distributed algorithm for finding disjoint paths with minimum total length in wireless sensor networks
- Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
- Distributed exact weighted all-pairs shortest paths in near-linear time
- Distributed Graph Algorithms and their Complexity: An Introduction
- Distributed distance computation and routing with small messages
- The sparsest additive spanner via multiple weighted BFS trees
- Title not available (Why is that?)
- Efficient and Decentralized Polling Protocol for General Social Networks
- Near-optimal approximate shortest paths and transshipment in distributed and streaming models
- Low-congestion shortcuts without embedding
- Fast distributed algorithms for girth, cycles and small subgraphs
- The Sparsest Additive Spanner via Multiple Weighted BFS Trees
- Single-source shortest paths in the CONGEST model with improved bounds
- Fast approximate shortest paths in the congested clique
- Algebraic methods in the congested clique
- Improved hardness of approximation of diameter in the CONGEST model
- Distributed Spanner Approximation
- A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths
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)
