Content deleted Content added
m Reverted 1 edit by 189.156.187.30 (talk) to last revision by Nyxion303 |
No edit summary Tags: Reverted Mobile edit Mobile web edit |
||
Line 2:
The '''distributed minimum spanning tree (MST)''' 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]]. One important application of this problem is to find a tree that can be used for [[Broadcasting (computing)|broadcasting]]. In particular, if the cost for a message to pass through an edge in a graph is significant, an MST can minimize the total cost for a source process to communicate with all the other processes in the network.
The problem was first suggested and solved in <math>O(V \log V)</math> time in 1983 by Gallager ''et al.'',<ref name="GHS" /> where <math>V</math> is the number of vertices in the [[graph theory|graph]]. Later, the solution was improved to <math>O(V)</math><ref>[
</ref> and finally<ref>Juan Garay, Shay Kutten and
<math>O(\sqrt V \log^* V + D)</math> where ''D'' is the network, or graph diameter. A lower bound on the time complexity of the solution has been eventually shown to be<ref>[[David Peleg
<math>\Omega\left({\frac{\sqrt V}{\log V}+D}\right).</math>
| |||