A Simple Deterministic Distributed MST Algorithm with Near-Optimal Time and Message Complexities

DOI10.1145/3380546zbMath1491.68265arXiv1703.02411MaRDI QIDQ5133968

Michael Elkin

Publication date: 11 November 2020

Published in: Journal of the ACM, Proceedings of the ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

minimum spanning tree; distributed graph algorithms; Bellman-Ford algorithm; distributed shortest paths

Mathematics Subject Classification ID

68W40: Analysis of algorithms

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

05C85: Graph algorithms (graph-theoretic aspects)

68W15: Distributed algorithms