A SUBLINEAR TIME DISTRIBUTED ALGORITHM FOR MINIMUM-WEIGHT SPANNING-TREES

This paper considers the question of identifying the parameters govern ing the behavior of fundamental global network problems. Many papers o n distributed network algorithms consider the task of optimizing the r unning time successful when an O(n) bound is achieved on an n-vertex n etwork. We propose that a more sensitive parameter is the network's di ameter Diam. This is demonstrated in the paper by providing a distribu ted minimum-weight spanning tree algorithm whose time complexity is su blinear in n, but linear in Diam (specifically, O(Diam + n(epsilon) . log(double dagger) n) for epsilon = ln 3/ln 6 = 0:6131...). Our result is achieved through the application of graph decomposition and edge-e limination-by-pipelining techniques that may be of independent interes t.