Fast Distributed Construction of Smallk-Dominating Sets and Applications

This article presents a fast distributed algorithm to compute a smallk-dominating setD(for any fixedk) and to compute its induced graph partition (breaking the graph into radiuskclusters centered around the vertices ofD). The time complexity of the algorithm isO(klog*n). Smallk-dominating sets have applications in a number of areas, including routing with sparse routing tables, the design of distributed data structures, and center selection in a distributed network. The main application described in this article concerns a fast distributed algorithm for constructing a minimum-weight spanning tree (MST). On ann-vertex network of diameterd, the new algorithm constructs an MST in time, improving on previous results.