Broadcast with partial knowledge
Baruch Awerbuch, Israel Cidon, et al.
PODC 1991
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.
Baruch Awerbuch, Israel Cidon, et al.
PODC 1991
Baruch Awerbuch, Amotz Bar-Noy, et al.
Journal of Algorithms
David Peleg, Barbara Simons
Information and Computation
Shay Kutten, David Peleg
Journal of Algorithms