Content deleted Content added
m Typo fixing, typos fixed: et al → et al. using AWB |
m authorlink |
||
Line 2:
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
<ref>Juan Garay, Shay Kutten and David Peleg, "A Sub-Linear Time Distributed Algorithm for Minimum-Weight Spanning Trees (Extended Abstract)", IEEE Symposium on Foundations of Computer Science, 1993.</ref>
| |||