A Faster Distributed Approximation Scheme for the Connected Dominating Set Problem for Growth-Bounded Graphs

摘要

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(T_(MIS) + 1/ε~(O(1)) · log~* n) synchronous rounds, where T_(MIS) 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 A is the maximum degree of the network graph. If one allows randomization, the running time reduces to O((log log n + 1/ε~(O(1))· log~* n) rounds.