期刊
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS
卷 44, 期 5, 页码 286-302出版社
ELSEVIER
DOI: 10.1016/j.comgeo.2010.12.003
关键词
Unit disc graph; k-Centre; Intersection graph; Facility location; Wireless networks
资金
- NSERC
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据