Linear-time sub-5 approximation for dominating sets in unit disk graphsReportar como inadecuado



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


Linear-time sub-5 approximation for dominating sets in unit disk graphs - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Descargar gratis o leer online en formato PDF el libro: 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.



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

Fuente: https://archive.org/



DESCARGAR PDF




Documentos relacionados