local approximation schemes for ad hoc and sensor networks
We present two local approaches that yield polynomial-time approximation schemes (PTAS) for the Maximum Independent Set and Minimum Dominating Set problem in unit disk graphs. The algorithms run locally in each node and compute a (1+?) -approximation to the problems at hand for any given ? > 0 . The time complexity of both algorithms is O(T MIS + log * ! n/? O(1) ) , where T MIS is the time required to compute a maximal independent set in the graph, and n denotes the number of nodes. We then extend these results to a more general class of graphs in which the maximum number of pair-wise independent nodes in every r -neighborhood is at most polynomial in r . Such graphs of polynomially bounded growth are introduced as a more realistic model for wireless networks and they generalize existing models, such as unit disk graphs or coverage area graphs.
locality approximation scheme sensor networks yield polynomial maximum independent set minimum dominating set dominating set graph algorithm computation timing time complexity general class model wireless networks coverage wireless ad hoc networks distributed algorithm ad-hoc