Approximating minimum independent dominating sets in wireless networks

Johann L. Hurink; T. Nieberg

doi:10.1016/j.ipl.2008.09.021

Approximating minimum independent dominating sets in wireless networks

Johann L. Hurink, T. Nieberg

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

13 Citations (Scopus)

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.

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	https://doi.org/10.1016/j.ipl.2008.09.021
Publication status	Published - 2008

Keywords

IR-62559
EWI-14222
METIS-252125

Access to Document

10.1016/j.ipl.2008.09.021

http://eprints.eemcs.utwente.nl/secure2/14222/01/Inf-Proc-Let.pdf

Cite this

Hurink, J. L., & Nieberg, T. (2008). Approximating minimum independent dominating sets in wireless networks. Information processing letters, 109(08332/2), 155-160. [10.1016/j.ipl.2008.09.021]. https://doi.org/10.1016/j.ipl.2008.09.021

@article{22763af47c5d4cbcaa6cd8a172c733a9,

title = "Approximating minimum independent dominating sets in wireless networks",

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.",

keywords = "IR-62559, EWI-14222, METIS-252125",

author = "Hurink, {Johann L.} and T. Nieberg",

note = "10.1016/j.ipl.2008.09.021",

year = "2008",

doi = "10.1016/j.ipl.2008.09.021",

language = "Undefined",

volume = "109",

pages = "155--160",

journal = "Information processing letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "08332/2",

}

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 -