@article {17638, title = {On the Complexity of Distributed Network Decomposition}, journal = {Journal of Algorithms}, volume = {20}, year = {1996}, month = {1996/03//}, pages = {356 - 374}, abstract = {In this paper, we improve the bounds for computing a network decomposition distributively and deterministically. Our algorithm computes an (nϵ(n),nϵ(n))-decomposition innO(ϵ(n))time, where[formula]. As a corollary we obtain improved deterministic bounds for distributively computing several graph structures such as maximal independent sets and Δ-vertex colorings. We also show that the class of graphs G whose maximum degree isnO(δ(n))where δ(n)=1/log lognis complete for the task of computing a near-optimal decomposition, i.e., a (logn, logn)-decomposition, in polylog(n) time. This is a corollary of a more general characterization, which pinpoints the weak points of existing network decomposition algorithms. Completeness is to be intended in the following sense: if we have an algorithmAthat computes a near-optimal decomposition in polylog(n) time for graphs inG, then we can compute a near-optimal decomposition in polylog(n) time for all graphs.}, isbn = {0196-6774}, doi = {10.1006/jagm.1996.0017}, url = {http://www.sciencedirect.com/science/article/pii/S0196677496900176}, author = {Panconesi,Alessandro and Srinivasan, Aravind} }