Time-communication trade-offs for minimum spanning tree construction
Ali Mashreghi, Valerie Jean King · 2017
This paper concerns the problem of constructing a minimum spanning tree (MST) in a synchronous distributed network with n nodes, where each node knows only the identities of itself and its neighbors. We assume the CONGEST model where messages are of size O(log n) bits. Spanning tree construction was long believed to require an amount of communication linear in the number of edges. In 2015, King, Kutten and Thorup presented a Monte Carlo algorithm which broke this communication bound. In particular it showed that an MST could be constructed with time and message complexity O(n log2 n/log log n), independent of the number of edges.