A PTAS for the minimum weight connected vertex cover P-3 problem on unit disk graphs
A PTAS for the minimum weight connected vertex cover P-3 problem on unit disk graphs
复制标题
单位圆盘图上最小权连通顶点覆盖P-3问题的PTAS
DOI：
10.1016/j.tcs.2015.01.005
复制
发表时间：
2015
影响因子：
1.1
通讯作者：
Broersma Hajo
中科院分区：
文献类型：
--
作者：
Wang Limin;Zhang Xiaoyan;Zhang Zhao;Broersma Hajo
设G=（V，E）是一个权图，即G的点权函数为w：V→ R+.研究了图G的一个最小权连通子图的确定问题，该子图至少有一个顶点与图G中所有长度为2的路公共。对于一般的图，这个问题是NP-难的。我们首先表明，它仍然是NP-难时，仅限于单位盘图。我们的主要贡献是这个问题的多项式时间近似计划，如果我们假设这个问题是c-本地和单位盘图的最小度至少为2。
Abstract Let G=(V, E) be a weighted graph, ie, with a vertex weight function w: V→ R+. We study the problem of determining a minimum weight connected subgraph of G that has at least one vertex in common with all paths of length two in G. It is known that this problem is NP-hard for general graphs. We first show that it remains NP-hard when restricted to unit disk graphs. Our main contribution is a polynomial time approximation scheme for this problem if we assume that the problem is c-local and the unit disk graphs have minimum degree of at least two.