Approximating minimum independent dominating sets in wireless networks


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
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
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: 252125