FAST DISTRIBUTED NETWORK DECOMPOSITIONS AND COVERS

Authors
AWERBUCH B BERGER B COWEN L PELEG D
Citation
B. Awerbuch et al., FAST DISTRIBUTED NETWORK DECOMPOSITIONS AND COVERS, Journal of parallel and distributed computing, 39(2), 1996, pp. 105-114
Citations number
22
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Journal of parallel and distributed computing → ACNP
ISSN journal
07437315
Volume
39
Issue
2
Year of publication
1996
Pages
105 - 114
Database
ISI
SICI code
0743-7315(1996)39:2<105:FDNDAC>2.0.ZU;2-F
Abstract
This paper presents deterministic sublinear-time distributed algorithm s for network decomposition and for constructing a sparse neighborhood cover of a network. The latter construction leads to improved distrib uted preprocessing time for a number of distributed algorithms, includ ing all-pairs shortest paths computation, load balancing, broadcast, a nd-bandwidth management. (C) 1996 Academic Press, Inc.