Distributed exact weighted all-pairs shortest paths in near-linear time

DOI10.1145/3313276.3316326zbMath1433.68595arXiv1811.03337OpenAlexW2962960360MaRDI QIDQ5212774

Danupon Nanongkai, Aaron Bernstein

Publication date: 30 January 2020

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

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

zbMATH Keywords

graph algorithmsdistributed computingCONGESTall-pairs shortest paths

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items

Single-source shortest paths in the CONGEST model with improved bounds, A distributed algorithm for directed minimum-weight spanning tree, The sparsest additive spanner via multiple weighted BFS trees, Fast approximate shortest paths in the congested clique