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

摘要

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