Content deleted Content added
fmt |
m Typo fixing, typos fixed: et al → et al. using AWB |
||
Line 1:
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 <math>O(V \log V)</math> time in 1983 by Gallagher et al. <ref>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.</ref>, 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 Annual ACM Symposium on Theory of Computing (STOC), New York City, New York, May 1987.
</ref> and finally
Line 29:
<references/>
[[Category:Spanning tree]]
| |||