Local Approximation Schemes for Ad Hoc and Sensor Networks


Kuhn, F. and Moscibroda, T. and Nieberg, T. and Wattenhofer, R. (2005) Local Approximation Schemes for Ad Hoc and Sensor Networks. In: 2005 Joint Workshop on Foundations of Mobile Computing, 02 Sep 2005, Cologne, Germany (pp. pp. 91-106).

open access
Abstract: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.
Item Type:Conference or Workshop Item
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/65539
Official URL:http://doi.acm.org/10.1145/1080810.1080827
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 226110