Sublinear Fully Distributed Partition with Applications |
| |
Authors: | Bilel Derbel Mohamed Mosbah Akka Zemmari |
| |
Affiliation: | 1. LIFL, INRIA, Université des Sciences et Technologies de Lille Batiment M3, 59655, Villeneuve d’Ascq Cedex, France 2. LaBRI, Université Bordeaux I, ENSEIRB, 351 Cours de la Libération, 33405, Talence, France
|
| |
Abstract: | We present new efficient deterministic and randomized distributed algorithms for decomposing a graph with n nodes into a disjoint set of connected clusters with radius at most k−1 and having O(n
1+1/k
) intercluster edges. We show how to implement our algorithms in the distributed
CONGEST\mathcal{CONGEST}
model of computation, i.e., limited message size, which improves the time complexity of previous algorithms (Moran and Snir
in Theor. Comput. Sci. 243(1–2):217–241, 2000; Awerbuch in J. ACM 32:804–823, 1985; Peleg in Distributed Computing: A Locality-Sensitive Approach, 2000) from O(n) to O(n
1−1/k
). We apply our algorithms for constructing low stretch graph spanners and network synchronizers in sublinear deterministic
time in the
CONGEST\mathcal{CONGEST}
model. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|