论文标题
单位磁盘图上的广义独立和主导集问题
The Generalized Independent and Dominating Set Problems on Unit Disk Graphs
论文作者
论文摘要
在本文中，我们研究了最大独立集和最小主导集问题的广义版本，即，最大$ d $ d $ distance独立集问题和最低$ d $ d $ d $ distance主导的设置问题，用于正整数$ d> 0 $。我们首先表明，最多$ d $ d $ distance独立集问题和最低$ d $ d $ distance totrations opar的设置问题属于NP-HARD类。接下来，我们为这两个问题提出了一种简单的多项式恒定因素近似算法和PTA。
In this article, we study a generalized version of the maximum independent set and minimum dominating set problems, namely, the maximum $d$-distance independent set problem and the minimum $d$-distance dominating set problem on unit disk graphs for a positive integer $d>0$. We first show that the maximum $d$-distance independent set problem and the minimum $d$-distance dominating set problem belongs to NP-hard class. Next, we propose a simple polynomial-time constant-factor approximation algorithms and PTAS for both the problems.
