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(TMIS + log*! n/εO(1)), where TMIS 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.
|Title of host publication||2005 Joint Workshop on Foundations of Mobile Computing|
|Editors||S Banerjee, S. Ganguly|
|Place of Publication||New York, USA|
|Number of pages||7|
|Publication status||Published - 2 Sep 2005|
- EC Grant Agreement nr.: FP6/004400