Linear Time Approximation for Dominating Sets and Independent Dominating Sets in Unit Disk Graphs

Details Linear Time Approximation for Dominating Sets and Independent Dominating Sets in Unit Disk Graphs Linear Time Approximation for Dominating Sets and Independent Dominating Sets in Unit Disk Graphs

2012-04-16

arxiv.org/abs/1204.3488v1

Computer Science

Data Structures and Algorithms

Scientific paper

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. Since the minimum dominating set problem for unit disk graphs is NP-hard, several approximation algorithms with different merits have been proposed in the literature. On one extreme, there is a linear time 5-approximation algorithm. On another extreme, there are two PTAS whose running times are polynomials of very high degree. We introduce a linear time approximation algorithm that takes the usual adjacency representation of the graph as input and attains a 4.888... approximation factor. This approximation factor is also attained by a second algorithm we present, which takes the geometric representation of the graph as input and runs in O(n log n) time, regardless of the number of edges. The analysis of the approximation factor of the algorithms, both of which are based on local improvements, exploits an assortment of results from discrete geometry to prove that certain graphs cannot be unit disk graphs. It is noteworthy that the dominating sets obtained by our algorithms are also independent sets.

Affiliated with

Also associated with

No associations

Rating

Linear Time Approximation for Dominating Sets and Independent Dominating Sets in Unit Disk Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Linear Time Approximation for Dominating Sets and Independent Dominating Sets in Unit Disk Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linear Time Approximation for Dominating Sets and Independent Dominating Sets in Unit Disk Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-6642