期刊
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS
卷 68, 期 -, 页码 62-76出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.comgeo.2017.06.002
关键词
Intersection graphs; Connectivity problems; NP-hardness problems; Approximation; Upper and lower bounds
资金
- National Science Foundation [CCF-1054779, IIS-1319573, CCF-1018388, CCF-1526406]
- Binational Science Foundation [BSF 2010074]
- Sandia National Labs, an NSERC
- NSERC
- Division of Computing and Communication Foundations
- Direct For Computer & Info Scie & Enginr [1526406] Funding Source: National Science Foundation
We consider the problem of assigning radii to a given set of points in the plane, such that the resulting set of disks is connected, and the sum of radii is minimized. We prove that the problem is NP-hard in planar weighted graphs if there are upper bounds on the radii and sketch a similar proof for planar point sets. For the case when there are no upper bounds on the radii, the complexity is open; we give a polynomial-time approximation scheme. We also give constant-factor approximation guarantees for solutions with a bounded number of disks; these results are supported by lower bounds, which are shown to be tight in some of the cases. Finally, we show that the problem is polynomially solvable if a connectivity tree is given, and we conclude with some experimental results. (C) 2017 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据