Distributed exact shortest paths in sublinear time

DOI10.1145/3055399.3055452zbMath1369.68344arXiv1703.01939OpenAlexW2592613193MaRDI QIDQ4978021

Michael Elkin

Publication date: 17 August 2017

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

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

zbMATH Keywords

shortest pathsdistributed algorithmsdistributed graph algorithmssublinear timeshortest paths tree

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items (12)

Latency, capacity, and distributed minimum spanning trees ⋮ Single-source shortest paths in the CONGEST model with improved bounds ⋮ The sparsest additive spanner via multiple weighted BFS trees ⋮ Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model ⋮ Unnamed Item ⋮ Depth First Search in the Semi-streaming Model ⋮ 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 ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC ⋮ Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time

This page was built for publication: Distributed exact shortest paths in sublinear time