A Fast Network-Decomposition Algorithm and its Applications to Constant-Time Distributed Computation

Leonid Barenboim, Michael Elkin, Cyril Gavoille

A partition $(C_1,C_2,...,C_q)$ of $G=(V,E)$ into clusters of strong (respectively, weak) diameter $d$, such that the supergraph obtained by contracting each $C_i$ is $\ell$-colo…