The Maximum Distance-d Independent Set Problem on Unit Disk Graphs
The Maximum Distance-d Independent Set Problem on Unit Disk Graphs
复制标题
单位圆盘图上的最大距离-d独立集问题
DOI：
10.1007/978-3-319-78455-7_6
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
S. Nandy
中科院分区：
文献类型：
--
作者：
S. Jena;Ramesh K. Jallu;G. Das;S. Nandy
本文研究了单位圆图上的最大距离相关集问题，它是极大独立集问题的一个变种。我们首先证明了该问题是NP难的。接下来，我们提出了一个多项式时间常数因子近似算法和一个求解该问题的PTAS算法。
In this article, we study the maximum distance-dindependent set problem, a variant of the maximum independent set problem, on unit disk graphs. We first show that the problem is NP-hard. Next, we propose a polynomial-time constant-factor approximation algorithm and a PTAS for the problem.