Paper Info
Title
Constant-factor approximation for minimum-weight (connected) dominating sets in unit disk graphs
Abstract
For a given graph with weighted vertices, the goal of the minimum-weight dominating set problem is to compute a vertex subset of smallest weight such that each vertex of the graph is contained in the subset or has a neighbor in the subset. A unit disk graph is a graph in which each vertex corresponds to a unit disk in the plane and two vertices are adjacent if and only if their disks have a non-empty intersection. We present the first constant-factor approximation algorithm for the minimum-weight dominating set problem in unit disk graphs, a problem motivated by applications in wireless ad-hoc networks. The algorithm is obtained in two steps: First, the problem is reduced to the problem of covering a set of points located in a small square using a minimum-weight set of unit disks. Then, a constant-factor approximation algorithm for the latter problem is obtained using enumeration and dynamic programming techniques exploiting the geometry of unit disks. Furthermore, we also show how to obtain a constant-factor approximation algorithm for the minimum-weight connected dominating set problem in unit disk graphs.
Year
DOI
Venue
2006
10.1007/11830924_3
APPROX-RANDOM
Keywords
Field
DocType
vertex subset,latter problem,unit disk,unit disk graph,dynamic programming technique,weighted vertex,constant-factor approximation algorithm,small square,constant-factor approximation,non-empty intersection,vertex corresponds,wireless ad hoc network,point location,dominating set,connected dominating set
Discrete mathematics,Dominating set,Combinatorics,Vertex (graph theory),Neighbourhood (graph theory),Independent set,Vertex cover,Feedback vertex set,Mathematics,Distributed computing,Maximal independent set,Unit disk graph
Conference
Volume
ISSN
ISBN
4110
0302-9743
3-540-38044-2
Citations 
PageRank 
References 
73
2.36
15
Authors
4
Name
Order
Citations
PageRank
Christoph Ambühl135718.50
Thomas Erlebach21233102.74
Matúš Mihalák319911.60
Marc Nunkesser424512.90