Distributed strong diameter network decomposition.

For a pair of positive parameters D , χ , a partition P of the vertex set V of an n -vertex graph G = (V , E) into disjoint clusters of diameter at most D each is called a (D , χ) network decomposition , if the supergraph G (P) , obtained by contracting each of the clusters of P , can be properly χ -colored. The decomposition P is said to be strong (resp., weak) if each of the clusters has strong (resp., weak) diameter at most D , i.e., if for every cluster C ∈ P and every two vertices u , v ∈ C , the distance between them in the induced graph G (C) of C (resp., in G) is at most D. Network decomposition is a powerful construct, very useful in distributed computing and beyond. In this paper we show that strong (O (log ⁡ n) , O (log ⁡ n)) network decompositions can be computed in O (log 2 ⁡ n) time in the CONGEST model. We also present a tradeoff between parameters of our network decomposition. Our work is inspired by and relies on the "shifted shortest path approach", due to Blelloch et al. [11] , and Miller et al. [20]. These authors developed this approach for PRAM algorithms for padded partitions. We adapt their approach to network decompositions in the distributed model of computation. [ABSTRACT FROM AUTHOR]