@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}
}
