Approximating minimum independent dominating sets in wireless networks

Johann L. Hurink, Tim Nieberg

Research output: Contribution to journalArticleAcademicpeer-review

14 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 languageEnglish
Pages (from-to)155-160
Number of pages6
JournalInformation processing letters
Volume109
Issue number2
DOIs
Publication statusPublished - 2008

Keywords

  • Approximation algorithms
  • PTAS
  • Minimum independent dominating set
  • Minimum maximal independent set

Fingerprint

Dive into the research topics of 'Approximating minimum independent dominating sets in wireless networks'. Together they form a unique fingerprint.

Cite this