22. Efficient Algorithms for Constructing Network Decompositions
Society for Industrial and Applied Mathematics eBooks · 2000
This chapter concerns fast distributed algorithms for constructing a network decomposition. The centralized algorithm presented in Section 14.2 is inherently sequential and its distributed implementation will require at least Ω(n) time. Here we present a faster (deterministic) distributed algorithm for the problem on unweighted graphs in the synchronous, congestion-free model, based on a different approach. 22.1 Constructing s-separated, r-ruling sets Let us first define the following notion. Definition 22.1.1 [s-separated, r-ruling set]: An s-separated, r-ruling set (or simply an (s, r)-set) in a graph G is a set of vertices with the following two properties. 1. for every , and 2. for every there exists some such that . We would like to associate with an (s, r)-set W for G a partition of the vertices of G into connected clusters, , such that and for every . We refer to this partition, illustrated in Figure 22.1, as the (s, r)-partition associated with W. The simple rule of placing each vertex in the cluster built around the closest element of W (i.e., placing v in some cluster such that for every ) can cause the formation of disconnected clusters (see Exercise 1). However, this problem can be corrected by using a modified rule based on breaking ties in a consistent manner (say, preferring the element with the smallest ID from among those closest to v). Consequently, we construct the (s, r)-partition associated with W using Procedure Sep_Rule_Part given in Figure 22.2. Lemma 22.1.2 The clusters of the collection defined by Procedure Sep_Rule_Part are guaranteed to be connected.