Content deleted Content added
mNo edit summary |
Add the reference to the upper bound |
||
Line 2:
The problem was first suggested and solved in <math>O(V \log V)</math> time in 1983 by Gallager et. al.,<ref>[[Robert G. Gallager]], Pierre A. Humblet, and P. M. Spira, “A distributed algorithm for minimum-weight spanning trees,” ''ACM Transactions on Programming Languages and Systems'', 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 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),” ''Proceedings of the IEEE [[Symposium on Foundations of Computer Science]]'' (FOCS), 1993.</ref> <ref>Shay Kutten and [[David Peleg]], “Fast Distributed Construction of Smallk-Dominating Sets and Applications,” ''Journal of Algorithms'', Volume 28, Issue 1, July 1998, Pages 40-66.</ref>
<math>O(\sqrt V \log^* V + D)</math> where ''D'' is the network, or graph diameter. Lower bound on the time complexity of the solution has been eventually shown to be<ref>David Peleg and Vitaly Rubinovich “A near tight lower bound on the time complexity of Distributed Minimum Spanning Tree Construction,“ ''[[SIAM Journal on Computing]]'', 2000, and ''IEEE Symposium on Foundations of Computer Science (FOCS)'', 1999.</ref>
<math>\Omega\left({\frac{\sqrt V}{\log V}}\right).</math>
| |||