Approximating minimum independent dominating sets in wireless networks

Johann L. Hurink, T. Nieberg

Research output: Contribution to journalArticleAcademicpeer-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 languageUndefined
Article number10.1016/j.ipl.2008.09.021
Pages (from-to)155-160
Number of pages6
JournalInformation processing letters
Volume109
Issue number08332/2
DOIs
Publication statusPublished - 2008

Keywords

  • IR-62559
  • EWI-14222
  • METIS-252125

Cite this

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

}

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 journalArticleAcademicpeer-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 -