An almost linear time and O(nlogn+e) Messages distributed algorithm for minimum-weight spanning trees

Publisher Website
Google Scholar
Abstract
A distributed algorithm is presented that constructs the minimum-weight spanning tree of an undirected connected graph with distinct edge weights and distinct node identities. Initially each node knows only the weight of each of its adjacent edges. When the algorithm terminates, each node knows which of its adjacent edges are edges of the tree. For a graph with n nodes and e edges, the total number of messages required by our algorithm is at most 5nlogn+2e, and each message contains at most one edge weight or one node identity plus 3+logn bits. Although our algorithm has the same message complexity as the previously known algorithm by Gallager et al., the time complexity of our algorithm takes at most O(nG(n))+ time units, an improvement from Gallager's O(nlogn)+. A worst case O(nG(n)) is also possible.

This publication has 6 references indexed in Scilit: