Please use this identifier to cite or link to this item:
|Title:||On the Complexity of Distributed Network Decomposition|
|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|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Aug 15, 2018
WEB OF SCIENCETM
checked on Jul 23, 2018
checked on May 25, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.