Fast Distributed Network Decompositions and Covers |
| |
| Authors: | Baruch Awerbuch Bonnie Berger Lenore Cowen David Peleg |
| |
| Affiliation: | aDepartment of Computer Science, Johns Hopkins University, Baltimore, Maryland, 21218;bDepartment of Mathematics and Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts, 02139;cDepartment of Mathematical Sciences, Johns Hopkins University, Baltimore, Maryland, 21218;dDepartment of Applied Mathematics and Computer Science, the Weizmann Institute, Rehovot, 76100, Israel |
| |
| Abstract: | 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
