Approximating Minimum Independent Dominating Sets in Wireless Networks
Hurink, J.L. and Nieberg, T. (2007) Approximating Minimum Independent Dominating Sets in Wireless Networks. [Report]

PDF
546kB 
Abstract:  We present the first polynomialtime 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+") pproximate minimum dominating set, or a certificate showing that the input graph does not reflect a wireless network. 
Item Type:  Report 
Faculty:  Electrical Engineering, Mathematics and Computer Science (EEMCS) 
Research Group:  
Link to this item:  http://purl.utwente.nl/publications/57741 
Official URL:  http://eprints.eemcs.utwente.nl/9436/ 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page
Metis ID: 242050