A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees
From MaRDI portal
Publication:4973061
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
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
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