Please use this identifier to cite or link to this item:
|Title:||On the Complexity of Distributed Network Decomposition||Authors:||Panconesi, A.
|Issue Date:||Mar-1996||Citation:||Panconesi, A., Srinivasan, A. (1996-03). On the Complexity of Distributed Network Decomposition. Journal of Algorithms 20 (2) : 356-374. ScholarBank@NUS Repository. https://doi.org/10.1006/jagm.1996.0017||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 in nO(∈(n)) time, where ∈(n) = 1/ √log n. 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 Script G sign whose maximum degree is nO(δ(n)) where δ(n) = 1/log log n is complete for the task of computing a near-optimal decomposition, i.e., a (log n, log n)-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 algorithm Script A sign that computes a near-optimal decomposition in polylog(n) time for graphs in Script G sign then we can compute a near-optimal decomposition in polylog(n) time for all graphs. © 1996 Academic Press, Inc.||Source Title:||Journal of Algorithms||URI:||http://scholarbank.nus.edu.sg/handle/10635/99360||ISSN:||01966774||DOI:||10.1006/jagm.1996.0017|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Feb 21, 2020
WEB OF SCIENCETM
checked on Feb 14, 2020
checked on Feb 16, 2020
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.