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)
48 Downloads (Pure)

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

Publication series

Name
PublisherACM Press

Keywords

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

Cite this

Kuhn, F., Moscibroda, T., Nieberg, T., & Wattenhofer, R. (2005). Local Approximation Schemes for Ad Hoc and Sensor Networks. In S. Banerjee, & S. Ganguly (Eds.), 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
Kuhn, F. ; Moscibroda, T. ; Nieberg, T. ; Wattenhofer, R. / Local Approximation Schemes for Ad Hoc and Sensor Networks. 2005 Joint Workshop on Foundations of Mobile Computing. editor / S Banerjee ; S. Ganguly. New York, USA : ACM Press, 2005. pp. 91-106
@inproceedings{0749bfd6173c4a0da90216daadecc64a,
title = "Local Approximation Schemes for Ad Hoc and Sensor Networks",
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.",
keywords = "EC Grant Agreement nr.: FP6/004400, EWI-1687, IR-65539, METIS-226110",
author = "F. Kuhn and T. Moscibroda and T. Nieberg and R. Wattenhofer",
year = "2005",
month = "9",
day = "2",
doi = "10.1145/1080810.1080827",
language = "Undefined",
isbn = "1-59593-092-2",
publisher = "ACM Press",
pages = "91--106",
editor = "S Banerjee and S. Ganguly",
booktitle = "2005 Joint Workshop on Foundations of Mobile Computing",

}

Kuhn, F, Moscibroda, T, Nieberg, T & Wattenhofer, R 2005, Local Approximation Schemes for Ad Hoc and Sensor Networks. in S Banerjee & S Ganguly (eds), 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.

2005 Joint Workshop on Foundations of Mobile Computing. ed. / S Banerjee; S. Ganguly. New York, USA : ACM Press, 2005. p. 91-106 10.1145/1080810.1080827.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-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 -

Kuhn F, Moscibroda T, Nieberg T, Wattenhofer R. Local Approximation Schemes for Ad Hoc and Sensor Networks. In Banerjee S, Ganguly S, editors, 2005 Joint Workshop on Foundations of Mobile Computing. New York, USA: ACM Press. 2005. p. 91-106. 10.1145/1080810.1080827 https://doi.org/10.1145/1080810.1080827