Distributed minimum spanning tree: Difference between revisions

Revision as of 15:33, 30 July 2006

Revision as of 20:42, 30 July 2006

Line 1:

{{Cleanup-date|July 2006}}

Distributed minimum spanning tree problem has similar meaning as [[Minimumminimum 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

:<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

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

== Model ==

Line 11 ⟶ 17:

As the output of the algorithm, every node knows which of its links belong to the Minimum Spanning Tree and which do not.

== References ==