A faster distributed approximation scheme for the connected dominating set problem for growth-bounded graphs
Beat Gfeller, Elias Vicari · 2011
Abstract. We present a distributed algorithm for finding a (1 + ε)-approximation of a Minimum Connected Dominating Set in the class of Growth-Bounded graphs, which includes Unit Disk graphs. In addition, the computed Connected Dominating Set guarantees a constant stretch factor on the length of a shortest path with respect to the original graph and induces a subgraph of constant degree. The nodes do not require any positioning or distance information. The algorithm runs in O TMIS + 1/ε O(1) · log ∗ n ´ synchronous rounds, where TMIS is the time for computing a Maximal Independent Set (MIS) in the network graph. Using the fastest known deterministic algorithm for computing a MIS, the total running time is O (log ∆ + 1/εO(1)) · log ∗ n, where ∆ is the maximum degree of the network graph. If one allows randomization, the running time can be reduced to O (log logn+ 1/εO(1)) · log ∗ n ´ rounds.