Approximation schemes for wireless networks

T. Nieberg, Johann L. Hurink, Walter Kern

Research output: Contribution to journalArticleAcademicpeer-review

40 Citations (Scopus)
4 Downloads (Pure)


Wireless networks are created by the communication links between a collection of radio transceivers. The nature of wireless transmissions does not lead to arbitrary undirected graphs but to structured graphs which we characterize by the polynomially bounded growth property. In contrast to many existing graph models for wireless networks, the property of polynomially bounded growth is defined independently of geometric data such as positional information. On such wireless networks, we present an approach that can be used to create polynomial-time approximation schemes for several optimization problems called the local neighborhood-based scheme. We apply this approach to the problems of seeking maximum (weight) independent sets and minimum dominating sets. These are two important problems in the area of wireless communication networks and are also used in many applications ranging from clustering to routing strategies. However, the approach is presented in a general fashion since it can be applied to other problems as well. The approach for the approximation schemes is robust in the sense that it accepts any undirected graph as input and either outputs a solution of desired quality or correctly asserts that the graph presented as input does not satisfy the structural assumption of a wireless network (an NP-hard problem).
Original languageUndefined
Article number10.1145/1383369.1383380
Pages (from-to)49
Number of pages17
JournalACM transactions on algorithms
Issue number4
Publication statusPublished - 2008


  • EWI-13450
  • IR-62468
  • METIS-255950
  • CR-G.2.2

Cite this