Distributed Minimum Spanning Tree - Overview

Overview

The input graph is considered to be a network, where vertices are independent computing nodes and edges are communication links. Links are weighted as in the classical problem.

At the beginning of the algorithm, nodes know only the weights of the links which are connected to them. (It is possible to consider models in which they know more, for example their neighbors' links.)

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

Read more about this topic:  Distributed Minimum Spanning Tree