View article

This paper presents a fast distributed algorithm to compute a small k-dominating set D (for any fixed k) and 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 via the scheme of [P~, the design of distributed data structures [P2], and center selection in a distributed network(cf.[BKP]). The main application described in this paper 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 (@ log* n+ d), improving on the results of [GKP]. The new MST algorithm is conceptually simpler than the three-phase algorithm of [GKP]. In addition to exploiting small k-dominating sets, it uses a very simple …