Distributed minimum spanning tree: Difference between revisions

Revision as of 13:41, 30 July 2006

Revision as of 15:33, 30 July 2006

Line 1:

{{Cleanup-date|July 2006}}

{{cleanup}}

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ůvkaBorů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({\frac{\sqrt V}{log V}})</math>.