A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees

DOI10.1145/3365005zbMath1454.68168arXiv1607.06883MaRDI QIDQ4973061

Gopal Pandurangan, Peter Robinson, Michele Scquizzato

Publication date: 2 December 2019

Published in: ACM Transactions on Algorithms, 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/1607.06883

zbMATH Keywords

distributed algorithms; minimum spanning trees

Mathematics Subject Classification ID

68W40: Analysis of algorithms

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

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W20: Randomized algorithms

68W15: Distributed algorithms