@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 = sep,

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",

}