Please use this identifier to cite or link to this item:
Title: On the Complexity of Distributed Network Decomposition
Authors: Panconesi, A.
Srinivasan, 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.
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
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 May 24, 2022


checked on May 24, 2022

Page view(s)

checked on May 26, 2022

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.