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

DOI10.1145/3365005zbMath1454.68168arXiv1607.06883OpenAlexW2985210774WikidataQ126808206 ScholiaQ126808206MaRDI QIDQ4973061

Gopal Pandurangan, Michele Scquizzato, Peter Robinson

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 algorithmsminimum spanning trees

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (13)

Fast Distributed Approximation for TAP and 2-Edge-Connectivity ⋮ A distributed algorithm for directed minimum-weight spanning tree ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model ⋮ Low-congestion shortcut and graph parameters ⋮ Fast distributed approximation for TAP and 2-edge-connectivity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Message lower bounds via efficient network synchronization ⋮ Message Lower Bounds via Efficient Network Synchronization ⋮ Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time

This page was built for publication: A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees