A Simple Deterministic Distributed MST Algorithm with Near-Optimal Time and Message Complexities
From MaRDI portal
Publication:5133968
DOI10.1145/3380546zbMath1491.68265arXiv1703.02411OpenAlexW3014095280MaRDI QIDQ5133968
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
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)
Related Items (11)
Latency, capacity, and distributed minimum spanning trees ⋮ 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 ⋮ Fast distributed approximation for TAP and 2-edge-connectivity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree ⋮ Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
This page was built for publication: A Simple Deterministic Distributed MST Algorithm with Near-Optimal Time and Message Complexities
