AHSWN HomeIssue Contents

A Faster Distributed Approximation Scheme for the Connected Dominating Set Problem for Growth-Bounded Graphs
Beat Gfeller and Elias Vicari

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, and n is the number of nodes. Using the fastest known deterministic algorithm for computing a MIS, the total running time is O(1/εO(1) · log* n).

Keywords: Connected dominating set, growth-bounded graphs, distributed approximation schemes, distributed algorithms, ad hoc wireless network.

full text (IP)