On the Complexity of Distributed Network Decomposition

✍ Scribed by Alessandro Panconesi; Aravind Srinivasan

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 200 KB
• Volume: 20
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1996.0017

✦ Synopsis

In this paper, we improve the bounds for computing a network decomposition Ž ⑀ Ž n. ⑀ Ž n. . distributively and deterministically. Our algorithm computes an n , n -

Ž . decomposition in n

time, where ⑀ n s 1r 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 G G whose maximum degree is n

where ␦ n s 1rlog 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 A A that computes a near-optimal decomposition in polylog n time for graphs in G G, then we can compute a near-optimal decomposition in Ž . polylog n time for all graphs.