Distributed exact shortest paths in sublinear time

DOI10.1145/3055399.3055452zbMath1369.68344arXiv1703.01939MaRDI 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 paths; distributed algorithms; distributed graph algorithms; sublinear time; shortest paths tree

Mathematics Subject Classification ID

68W40: Analysis of algorithms

05C35: Extremal problems in graph theory

68R10: Graph theory (including graph drawing) in computer science

05C38: Paths and cycles

05C85: Graph algorithms (graph-theoretic aspects)

68W15: Distributed algorithms