%0 Journal Article %F DERBEL-2010-351045 %A Derbel, Bilel %A Mosbah, Mohamed %A Zemmari, Akka %T Sublinear Fully Distributed Partition with Applications %J Theory of Computing Systems %V 47 %N 3 %P 368-404 %X 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 $\mathcal{CONGEST}$ model of computation, i.e., limited message size, which improves the time complexity of previous algorithms\ \cite{MS00,Awe85,Peleg00b} 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 $\mathcal{CONGEST}$ model %U http://hal.archives-ouvertes.fr/hal-00351045 %D 2010