TR-07-17: Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graph

Abstract

We present local $1+\epsilon$ approximation algorithms for the minimum dominating and the connected dominating set problems in location aware Unit Disk Graphs (UDGs). Our algorithms are local in the sense that the status of a vertex $v$ (i.e. whether or not $v$ is part of the set to be computed) depends only on the vertices which are a constant number of edges (hops) away from $v$. This constant is independent of the size of the network. In our graph model we assume that each vertex knows its geographic coordinates in the plane (location aware nodes). Our algorithms give the best approximation ratios known for this setting. Moreover, the processing time that each vertex needs to determine whether or not it is part of the computed set is bounded by a polynomial in the number of vertices which are a constant number of hops away from it.

TR-07-17.pdf