Approximating minimum independent dominating sets in wireless networks

Johann L. Hurink, T. Nieberg

Research output: Book/ReportReportProfessional

230 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. Graphs of bounded growth are used to characterize wireless communication networks, and this class of graph includes many models known from the literature, e.g. (Quasi) Unit Disk Graphs. An independent dominating set is a dominating set in a graph that is also independent. It thus combines the advantages of both structures, and there are many applications that rely on these two structures e.g. in the area of wireless ad hoc networks. The presented approach yields a robust algorithm, that is, the algorithm accepts any undirected graph as input, and returns a $(1+\varepsilon )$-approximate minimum dominating set, or a certificate showing that the input graph does not reflect a wireless network.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Number of pages12
Publication statusPublished - 15 Feb 2007

Publication series

NameMemorandum Department of Applied Mathematics, University of Twente 1824
No.2/1824
ISSN (Print)1874-4850
ISSN (Electronic)1874-4850

Keywords

  • EWI-9436
  • IR-57741
  • METIS-242050

Cite this

Hurink, J. L., & Nieberg, T. (2007). Approximating minimum independent dominating sets in wireless networks. (Memorandum Department of Applied Mathematics, University of Twente 1824; No. 2/1824). Enschede: University of Twente, Department of Applied Mathematics.