Liar's Dominating Set in Unit Disk Graphs

摘要

In this article, we study a variant of the dominating set problem known as the liar's dominating set problem on unit disk graphs. We prove that the liar's dominating set problem is NP-complete and admits a polynomial time approximation scheme in unit disk graphs.