Distributed minimum spanning tree

Distributed Minimum Spanning Tree has similar meaning as Minimum Spanning Tree problem, but is different in definition of inputs/outputs and totally different solution approaches.

The problem was first suggested and solved in ${\displaystyle O(VlogV)}$ time in 1983. Later the solution was improved to ${\displaystyle O(V)}$ and finally ${\displaystyle O({\sqrt {V}}log*V+D)}$ where D is the network, or graph diameter.

Model

The input graph ${\displaystyle G(V,E)}$  is considered to be a network, where vertices ${\displaystyle V}$  are independent computing nodes and ${\displaystyle E}$  are communication links. Links are weighted as in classical problem.

At the beginning of the algorithm, all nodes know weights of the links which are connected to them. In general case, no node knows topology of the graph, although it is possible to consider models in which nodes know, for example, its neighbor's links.

As the output of the algorithm, every node knows which of its links belong to the Minimum Spanning Tree and which do not.

References

Robert G. Gallager, Pierre A. Humblet, and P. M. Spira, "A distributed algorithm for minimum-weight spanning trees," ACM TOPLAS,vol.5, no. 1, pp. 66--77, January 1983.