Theory Comput Syst DOI 10.1007/s00224-009-9190-x Sublinear Fully Distributed Partition with Applications

Abstract We present new efficient deterministic and randomized distributed algo-rithms for decomposing a graph with n nodes into a disjoint set of connected clusters with radius at most k − 1 and having O(n1+1/k) intercluster edges. We show how to implement our algorithms in the distributed C O N G E S T model of computation, i.e., limited message size, which improves the time complexity of previous algo-rithms (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(n1−1/k). We apply our algorithms for constructing low stretch graph spanners and network synchronizers in sublinear deterministic time in the C O N G E S T model