Distributed minimum spanning tree

You must add a |reason= parameter to this Cleanup template – replace it with {{Cleanup|July 2006|reason=<Fill reason here>}}, or remove the Cleanup template.
Distributed minimum spanning tree problem has similar meaning as minimum spanning tree problem, but is different in definition of inputs/outputs and is totally different in its solution approaches, although most basic paradigm resembles Borůvka's algorithm approach.

The problem was first suggested and solved in ${\displaystyle O(V\log V)}$ time in 1983 by Gallagher et al^[1]. 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. Lower bound on the time complexity of the solution has been eventually shown to be

${\displaystyle \Omega \left({\frac {\sqrt {V}}{\log V}}\right).}$

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 the 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

1. 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.

 2. B. Awerbuch. Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems. 

In Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC), New York City, New York, May 1987.