A.: Fast distributed graph partition and application

This paper presents efficient deterministic and ran-domized distributed algorithms for decomposing a graph with n nodes into a disjoint set of connected clusters with small radius and few intercluster edges. Our al-gorithms can be easily implemented in the distributed CONGEST model of computation i.e., limited message size, improving the time complexity of previous algo-rithms [27, 3, 29] from linear to sublinear. One im-portant application of our algorithms is efficient con-struction of sparse graph spanners. In fact, given a pa-rameter k, we show that there exists a sublinear deter-ministic distributed algorithm that constructs a graph spanner of stretch 2k−1 with at most O(n1+1/k) edges in the CONGEST model