Local Approximation Schemes for Ad Hoc and Sensor Networks
| Autor: | Kuhn, F., Moscibroda, T., Nieberg, T., Wattenhofer, R., Banerjee, S, Ganguly, S. |
|---|---|
| Přispěvatelé: | Discrete Mathematics and Mathematical Programming |
| Rok vydání: | 2005 |
| Předmět: | |
| Zdroj: | 2005 Joint Workshop on Foundations of Mobile Computing, 91-106 STARTPAGE=91;ENDPAGE=106;TITLE=2005 Joint Workshop on Foundations of Mobile Computing DIALM-POMC |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|