Juan A. Garay, Shay Kutten, et al.
SIAM Journal on Computing
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 logn). 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.
Juan A. Garay, Shay Kutten, et al.
SIAM Journal on Computing
Baruch Awerbuch, Shay Kutten, et al.
PODC 1991
Baruch Awerbuch, Shay Kutten, et al.
STOC 1993
Amotz Bar-Noy, Danny Dolev, et al.
Information and Computation