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 | |
Publication status | Published - 2008 |
Keywords
- Approximation algorithms
- PTAS
- Minimum independent dominating set
- Minimum maximal independent set