Abstract
| Original language | Undefined |
|---|---|
| Article number | 10.1016/j.ipl.2008.09.021 |
| Pages (from-to) | 155-160 |
| Number of pages | 6 |
| Journal | Information processing letters |
| Volume | 109 |
| Issue number | 08332/2 |
| DOIs | |
| Publication status | Published - 2008 |
Keywords
- IR-62559
- EWI-14222
- METIS-252125
Cite this
}
Approximating minimum independent dominating sets in wireless networks. / Hurink, Johann L.; Nieberg, T.
In: Information processing letters, Vol. 109, No. 08332/2, 10.1016/j.ipl.2008.09.021, 2008, p. 155-160.Research output: Contribution to journal › Article › Academic › peer-review
TY - JOUR
T1 - Approximating minimum independent dominating sets in wireless networks
AU - Hurink, Johann L.
AU - Nieberg, T.
N1 - 10.1016/j.ipl.2008.09.021
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 - IR-62559
KW - EWI-14222
KW - METIS-252125
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 - 08332/2
M1 - 10.1016/j.ipl.2008.09.021
ER -