A Simple Deterministic Distributed MST Algorithm, with Near-Optimal Time and Message Complexities
Michael Elkin · 2017
Distributed minimum spanning tree (MST) problem is one of the most central and fundamental problems in distributed graph algorithms. Kutten and Peleg [KP98] devised an algorithm with running time O(D + √n . log* n), where D is the hop-diameter of the input n-vertex m-edge graph, and with message complexity O(m + n3/2). Peleg and Rubinovich [PR99] showed that the running time of the algorithm of [KP98] is essentially tight, and asked if one can achieve near-optimal running time together with near-optimal message complexity.