Local Approximation Schemes for Ad Hoc and Sensor Networks


Share/Save/Bookmark

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.

[img]
Preview
PDF
170Kb
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
Faculty:
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
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 226110