On the Complexity of Distributed Network Decomposition

TitleOn the Complexity of Distributed Network Decomposition
Publication TypeJournal Articles
Year of Publication1996
AuthorsPanconesi A, Srinivasan A
JournalJournal of Algorithms
Volume20
Issue2
Pagination356 - 374
Date Published1996/03//
ISBN Number0196-6774
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 innO(ϵ(n))time, where[formula]. 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 G whose maximum degree isnO(δ(n))where δ(n)=1/log lognis complete for the task of computing a near-optimal decomposition, i.e., a (logn, logn)-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 algorithmAthat computes a near-optimal decomposition in polylog(n) time for graphs inG, then we can compute a near-optimal decomposition in polylog(n) time for all graphs.

URLhttp://www.sciencedirect.com/science/article/pii/S0196677496900176
DOI10.1006/jagm.1996.0017