Distributed minimum spanning tree
Encyclopedia
The distributed minimum spanning tree problem involves the construction of a minimum spanning tree
by a distributed algorithm, in a network where nodes communicate by message passing. It is radically different from the classical sequential problem, although the most basic approach resembles Borůvka's algorithm
.
The problem was first suggested and solved in
time in 1983 by Gallager et. al., where 
is the number of vertices in the graph
. Later the solution was improved to
and finally
where D is the network, or graph diameter. Lower bound on the time complexity of the solution has been eventually shown to be
-approximation algorithm was developed by Maleq Khan and Gopal Pandurangan. This algorithm runs in 
time, where 
is the local shortest path diameter of the 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.
Minimum spanning tree
Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees...
by a distributed algorithm, in a network where nodes communicate by message passing. It is radically different from the classical sequential problem, although the most basic approach resembles Borůvka's algorithm
Boruvka's algorithm
Borůvka's algorithm is an algorithm for finding a minimum spanning tree in a graph for which all edge weights are distinct.It was first published in 1926 by Otakar Borůvka as a method of constructing an efficient electricity network for Moravia....
.
The problem was first suggested and solved in
time in 1983 by Gallager et. al., where is the number of vertices in the graphGraph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
. Later the solution was improved to
and finally where D is the network, or graph diameter. Lower bound on the time complexity of the solution has been eventually shown to beApproximation algorithms
An-approximation algorithm was developed by Maleq Khan and Gopal Pandurangan. This algorithm runs in time, where is the local shortest path diameter of the graph.Model
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.