论文标题
骗子在单元磁盘图中的统治
Liar's Domination in Unit Disk Graphs
论文作者
论文摘要
在本文中，我们研究了最小统治者的最低统治设置问题的变体，称为最小骗子的主导集（MLDS）问题。我们证明了MLDS问题是单位磁盘图中的NP-HARD。 Next, we show that the recent sub-quadratic time $\frac{11}{2}$-factor approximation algorithm \cite{bhore} for the MLDS problem is erroneous and propose a simple $O(n + m)$ time 7.31-factor approximation algorithm, where $n$ and $m$ are the number of vertices and edges in the input unit disk graph, 分别。最后，我们证明MLDS问题允许多项式时间近似方案。
In this article, we study a variant of the minimum dominating set problem known as the minimum liar's dominating set (MLDS) problem. We prove that the MLDS problem is NP-hard in unit disk graphs. Next, we show that the recent sub-quadratic time $\frac{11}{2}$-factor approximation algorithm \cite{bhore} for the MLDS problem is erroneous and propose a simple $O(n + m)$ time 7.31-factor approximation algorithm, where $n$ and $m$ are the number of vertices and edges in the input unit disk graph, respectively. Finally, we prove that the MLDS problem admits a polynomial-time approximation scheme.
