Distributed minimum spanning tree: Difference between revisions

Revision as of 19:49, 13 September 2006

Revision as of 19:55, 13 September 2006

Line 4:

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>. Later the solution was improved to <math>O(V)</math>

<ref>B.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>

J.Juan Garay, S.Shay Kutten and D.David Peleg, "A Sub-Linear Time Distributed Algorithm for Minimum-Weight Spanning Trees (Extended Abstract)", IEEE Symposium on Foundations of Computer Science, 1993.

IEEE Symposium on Foundations of Computer Science, 1993.

</ref>

Line 14 ⟶ 13:

where ''D'' is the network, or graph diameter. Lower bound on the time complexity of the solution has been eventually shown to be

<ref>D.David Peleg and V.Vitaly Rubinovich “A near tight lower bound on the time complexity of Distributed Minimum Spanning Tree Construction”, SIAM Journal of Computing, 2000, and IEEE Foundations of Computer Science (FOCS) Symposium, 1999.</ref>

:<math>\Omega\left({\frac{\sqrt V}{\log V}}\right).</math>