Approximation schemes for wireless networks

Research output: Contribution to journalArticleAcademicpeer-review

34 Citations (Scopus)

Abstract

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
Volume4
Issue number4
DOIs
Publication statusPublished - 2008

Keywords

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

Cite this