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