Approximating minimum independent dominating sets in wireless networks

Johann L. Hurink; Tim Nieberg

doi:10.1016/j.ipl.2008.09.021

Approximating minimum independent dominating sets in wireless networks

Johann L. Hurink
, Tim Nieberg

Discrete Mathematics and Mathematical Programming

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

32 Citations (Scopus)

6 Downloads (Pure)

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	English
Pages (from-to)	155-160
Number of pages	6
Journal	Information processing letters
Volume	109
Issue number	2
DOIs	https://doi.org/10.1016/j.ipl.2008.09.021
Publication status	Published - 2008

Keywords

Approximation algorithms
PTAS
Minimum independent dominating set
Minimum maximal independent set

Access to Document

10.1016/j.ipl.2008.09.021

Approximating minimum independent dominating sets in wireless networks
Hurink, J. L. & Nieberg, T., 15 Feb 2007, Enschede: University of Twente. 12 p. (Memorandum; no. 1824)
Research output: Book/Report › Report › Professional

Open Access
File

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 = "Approximation algorithms, PTAS, Minimum independent dominating set, Minimum maximal independent set",

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

year = "2008",

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

language = "English",

volume = "109",

pages = "155--160",

journal = "Information processing letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "2",

}

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

SN - 0020-0190

VL - 109

SP - 155

EP - 160

JO - Information processing letters

JF - Information processing letters

IS - 2

ER -

Approximating minimum independent dominating sets in wireless networks

Abstract

Keywords

Access to Document

Fingerprint

Research output

Approximating minimum independent dominating sets in wireless networks

Cite this