Journal
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS
Volume 44, Issue 5, Pages 286-302Publisher
ELSEVIER
DOI: 10.1016/j.comgeo.2010.12.003
Keywords
Unit disc graph; k-Centre; Intersection graph; Facility location; Wireless networks
Categories
Funding
- NSERC
Ask authors/readers for more resources
Motivated by the gateway placement problem in wireless networks, we consider the geometric k-centre problem on unit disc graphs: given a set of points P in the plane, find a set F of k points in the plane that minimizes the maximum graph distance from any vertex in P to the nearest vertex in F in the unit disc graph induced by P boolean OR F. We show that the vertex 1-centre provides a 7-approximation of the geometric 1-centre and that a vertex k-centre provides a 13-approximation of the geometric k-centre, resulting in an O (kn)-time 26-approximation algorithm. We describe O(n(2)m)-time and O(n(3))-time algorithms, respectively, for finding exact and approximate geometric 1-centres, and an O(mn(2k))-time algorithm for finding a geometric k-centre for any fixed k. We show that the problem is NP-hard when k is an arbitrary input parameter. Finally, we describe an O(n)-time algorithm for finding a geometric k-centre in one dimension. (C) 2010 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available