Distributed minimum spanning tree: Difference between revisions

Revision as of 11:54, 30 July 2006

Revision as of 12:47, 30 July 2006

Line 1:

Distributed Minimumminimum Spanningspanning Treetree problem has similar meaning as [[Minimum Spanningspanning Treetree]] 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({\frac{\sqrt V}{log V}})</math>.

== Model ==

The input graph <math>G(V,E)</math> is considered to be a network, where vertices <math>V</math> are independent computing nodes and <math>E</math> are communication links. Links are weighted as in the classical problem.

At the beginning of the algorithm, all nodes know weights of the links which are connected to them. In general case, no node knows topology of the graph, although it is possible to consider models in which nodes know, for example, its neighbor's links.

Line 14:

== References ==

<references/>

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.