DISTRIBUTED CONSTRUCTION OF SMALL K-DOMINATING SETS AND APPLICATIONS

This article presents a fast distributed algorithm to compute a small k-dominating set D (for any fixed k) and to compute its induced graph partition (breaking the graph into radius k clusters centered around t he vertices of D). The time complexity of the algorithm is O(k log n) . Small k-dominating sets have applications in a number of areas, incl uding routing with sparse routing tables, the design of distributed da ta structures, and center selection in a distributed network. The main application described in this article concerns a fast distributed alg orithm for constructing a minimum-weight spanning tree (MST). On an n- vertex network of diameter d, the new algorithm constructs an MST in t ime O(root n logn + d), improving on previous results. (C) 1998 Acade mic Press.