Approximation schemes for wireless networks


Nieberg, T. and Hurink, J.L. and Kern, W. (2008) Approximation schemes for wireless networks. ACM Transactions on Algorithms, 4 (4). p. 49. ISSN 1549-6325

[img] PDF
Restricted to UT campus only
: Request a copy
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).

Item Type:Article
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Official URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 255950