Distributed minimum spanning tree: Difference between revisions

Revision as of 15:49, 4 September 2006

Revision as of 19:49, 13 September 2006

Line 2:

Distributed minimum spanning tree problem has similar meaning as [[minimum spanning tree]] problem, but is different in definition of inputs/outputs and is totally different in its solution approaches, although most basic paradigm resembles [[Borůvka's algorithm]] approach.

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> and finally

2. <ref>B. 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.Garay, S.Kutten and D.Peleg, "A Sub-Linear Time Distributed Algorithm for Minimum-Weight Spanning Trees (Extended Abstract)",

IEEE Symposium on Foundations of Computer Science, 1993.

</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>D.Peleg and V.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>

Line 23 ⟶ 31:

[[Category:Graph theory]]

2. B. Awerbuch. Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election, and Related Problems.

In Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC), New York City, New York, May 1987.