Local Approximation Schemes for Ad Hoc and Sensor Networks

F. Kuhn, T. Moscibroda, T. Nieberg, R. Wattenhofer

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

45 Citations (Scopus)
86 Downloads (Pure)


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.
Original languageUndefined
Title of host publication2005 Joint Workshop on Foundations of Mobile Computing
EditorsS Banerjee, S. Ganguly
Place of PublicationNew York, USA
PublisherACM Press
Number of pages7
ISBN (Print)1-59593-092-2
Publication statusPublished - 2 Sep 2005
Event2005 Joint Workshop on Foundations of Mobile Computing - Cologne, Germany
Duration: 2 Sep 20052 Sep 2005

Publication series

PublisherACM Press


Workshop2005 Joint Workshop on Foundations of Mobile Computing
Other02 Sep 2005


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

Cite this