Approximating minimum independent dominating sets in wireless networks

Share/Save/Bookmark

Hurink, J.L. and Nieberg, T. (2008) Approximating minimum independent dominating sets in wireless networks. Information Processing Letters, 109 (2). pp. 155-160. ISSN 0020-0190

[img] PDF
Restricted to UT campus only
: Request a copy
174kB
Abstract:We present the first polynomial-time approximation scheme (PTAS) for the Minimum Independent Dominating Set problem in graphs of polynomially bounded growth which are used to model wireless communication networks.
The approach presented yields a robust algorithm, that is, it accepts any undirected graph as input, and returns a (1+ε)-approximate minimum independent dominating set, or a certificate showing that the input graph does not satisfy the bounded growth property.
Item Type:Article
Copyright:© 2008 Elsevier
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/62559
Official URL:http://dx.doi.org/10.1016/j.ipl.2008.09.021
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 252125