Fast distributed construction of small k-dominating sets and applications

Abstract

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 the 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, 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 an n-vertex network of diameter d, the new algorithm constructs an MST in time O(√n log* n +d), improving on previous results. © 1998 Academic Press.