Approximating minimum independent dominating sets in wireless networks |
| |
| Authors: | Johann L Hurink |
| |
| Affiliation: | a University of Twente, Faculty of Electrical Engineering, Mathematics and Computer Science, Postbus 217, NL-7500 AE Enschede, The Netherlands
b Research Institute for Discrete Mathematics, University of Bonn, Lennéstr. 2, D-53113 Bonn, Germany |
| |
| 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. |
| |
| Keywords: | Approximation algorithms PTAS Minimum independent dominating set Minimum maximal independent set |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
