Improved distributed algorithms for exact shortest paths

DOI10.1145/3188745.3188948zbMath1428.68379arXiv1712.09121OpenAlexW2963948050MaRDI QIDQ5230308

Jason Li, Mohsen Ghaffari

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

shortest pathsdistributed algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Distributed algorithms (68W15)

Related Items (8)

Single-source shortest paths in the CONGEST model with improved bounds ⋮ A novel pseudo‐polynomial approach for shortest path problems ⋮ A distributed algorithm for directed minimum-weight spanning tree ⋮ The sparsest additive spanner via multiple weighted BFS trees ⋮ The Sparsest Additive Spanner via Multiple Weighted BFS Trees ⋮ Fast approximate shortest paths in the congested clique ⋮ Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models ⋮ Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time

This page was built for publication: Improved distributed algorithms for exact shortest paths