Fast Distributed Construction of a Small k-Dominating
Sets and Applications
Shay Kutten David Peleg
July 29, 1997
Abstract
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 [PU], 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(sqrt(n)log*n + d), improving on the results of [GKP].