Content deleted Content added
No edit summary Tags: Reverted Mobile edit Mobile web edit |
Reverted 1 edit by 189.156.187.30 (talk): Rv; removed with no reason |
||
Line 1:
[[Image:Minimum spanning tree.svg|thumb|400px|right|''Example of a MST:'' The minimum spanning tree of a [[planar graph]]. Each edge is labeled with its weight, which here is roughly proportional to its length.]]
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>[[Baruch Awerbuch]]. “Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems,” ''Proceedings of the 19th ACM [[Symposium on Theory of Computing]] (STOC)'', New York City, New York, May 1987.
| |||