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 Feb 21, 2020


checked on Feb 14, 2020

Page view(s)

checked on Feb 16, 2020

Google ScholarTM



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