TY - JOUR
T1 - Approximating minimum independent dominating sets in wireless networks
AU - Hurink, Johann L.
AU - Nieberg, Tim
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
KW - Approximation algorithms
KW - PTAS
KW - Minimum independent dominating set
KW - Minimum maximal independent set
U2 - 10.1016/j.ipl.2008.09.021
DO - 10.1016/j.ipl.2008.09.021
M3 - Article
VL - 109
SP - 155
EP - 160
JO - Information processing letters
JF - Information processing letters
SN - 0020-0190
IS - 2
ER -