Back to Search
Start Over
The Generalized Independent and Dominating Set Problems on Unit Disk Graphs
- Publication Year :
- 2020
-
Abstract
- 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.
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2006.15381
- Document Type :
- Working Paper