Linear-time sub-5 approximation for dominating sets in unit disk graphsReport as inadecuate



 Linear-time sub-5 approximation for dominating sets in unit disk graphs


Linear-time sub-5 approximation for dominating sets in unit disk graphs - Download this document for free, or read online. Document in PDF available to download.

Download or read this book online for free in PDF: Linear-time sub-5 approximation for dominating sets in unit disk graphs
A unit disk graph is the intersection graph of n congruent disks in the plane. Dominating sets in unit disk graphs are widely studied due to their application in wireless ad-hoc networks. Because the minimum dominating set problem for unit disk graphs is NP-hard, numerous approximation algorithms have been proposed in the literature, including some PTAS. However, since the proposal of a linear-time 5-approximation algorithm in 1995, the lack of efficient algorithms attaining better approximation factors has aroused attention. We introduce a linear-time On+m approximation algorithm that takes the usual adjacency representation of the graph as input and outputs a 44-9-approximation. This approximation factor is also attained by a second algorithm, which takes the geometric representation of the graph as input and runs in On log n time regardless of the number of edges. Additionally, we propose a 43-9-approximation which can be obtained in On^2 m time given only the graphs adjacency representation. It is noteworthy that the dominating sets obtained by our algorithms are also independent sets.



Author: Guilherme D. da Fonseca; Celina M. H. de Figueiredo; Vinícius G. P. de Sá; Raphael Machado

Source: https://archive.org/



DOWNLOAD PDF




Related documents