### Abstract

Original language | Undefined |
---|---|

Title of host publication | 2005 Joint Workshop on Foundations of Mobile Computing |

Editors | S Banerjee, S. Ganguly |

Place of Publication | New York, USA |

Publisher | ACM Press |

Pages | 91-106 |

Number of pages | 7 |

ISBN (Print) | 1-59593-092-2 |

DOIs | |

Publication status | Published - 2 Sep 2005 |

### Publication series

Name | |
---|---|

Publisher | ACM Press |

### Keywords

- EC Grant Agreement nr.: FP6/004400
- EWI-1687
- IR-65539
- METIS-226110

### Cite this

*2005 Joint Workshop on Foundations of Mobile Computing*(pp. 91-106). [10.1145/1080810.1080827] New York, USA: ACM Press. https://doi.org/10.1145/1080810.1080827

}

*2005 Joint Workshop on Foundations of Mobile Computing.*, 10.1145/1080810.1080827, ACM Press, New York, USA, pp. 91-106. https://doi.org/10.1145/1080810.1080827

**Local Approximation Schemes for Ad Hoc and Sensor Networks.** / Kuhn, F.; Moscibroda, T.; Nieberg, T.; Wattenhofer, R.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Local Approximation Schemes for Ad Hoc and Sensor Networks

AU - Kuhn, F.

AU - Moscibroda, T.

AU - Nieberg, T.

AU - Wattenhofer, R.

PY - 2005/9/2

Y1 - 2005/9/2

N2 - 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.

AB - 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.

KW - EC Grant Agreement nr.: FP6/004400

KW - EWI-1687

KW - IR-65539

KW - METIS-226110

U2 - 10.1145/1080810.1080827

DO - 10.1145/1080810.1080827

M3 - Conference contribution

SN - 1-59593-092-2

SP - 91

EP - 106

BT - 2005 Joint Workshop on Foundations of Mobile Computing

A2 - Banerjee, S

A2 - Ganguly, S.

PB - ACM Press

CY - New York, USA

ER -