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.

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:	Discrete Mathematics and Mathematical Programming (DMMP)
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

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 226110