| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427900 | Information Processing Letters | 2008 | 6 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
