A Fully Distributed Linear Time Algorithm for Cluster Network Decomposition

B. Derbel and M. Mosbah (France)


clustered representation, distributed algorithm, synchroniz ers


We present a linear time distributed algorithm for decom posing a graph into a disjoint set of clusters. This algorithm is truly parallel since many clusters can be constructed in parallel, which gives an answer to a question asked by S. Moran and S. Snir in [1]. Moreover, no precomputed span ning tree is required for the computation of clusters. We apply the designed algorithm to construct covers for syn chronizers 1 and 2.

Important Links:

Go Back