Fast Distributed Network Decompositions and Covers
Baruch Awerbuch, Bonnie Berger, Lenore Cowen, David Peleg · Journal of Parallel and Distributed Computing · 1996
This paper presents deterministic sublinear-time distributed algorithms for network decomposition and for constructing a sparse neighborhood cover of a network. The latter construction leads to improved distributed preprocessing time for a number of distributed algorithms, including all-pairs shortest paths computation, load balancing, broadcast, and bandwidth management.