Please use this identifier to cite or link to this item: https://doi.org/10.1006/jagm.1996.0017
Title: On the Complexity of Distributed Network Decomposition
Authors: Panconesi, A.
Srinivasan, A. 
Issue Date: Mar-1996
Source: 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.

SCOPUSTM   
Citations

81
checked on Feb 13, 2018

WEB OF SCIENCETM
Citations

49
checked on Feb 13, 2018

Page view(s)

22
checked on Feb 20, 2018

Google ScholarTM

Check

Altmetric


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