# The Generalized Independent and Dominating Set Problems on Unit Disk Graphs

Source: [The Generalized Independent and Dominating Set Problems on Unit Disk Graphs](<https://www.sota2.com/research/paper/68fa67d41e209131cea18c11>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T22:23:05.784Z

Authors: Sangram K. Jena, Ramesh K. Jallu, Gautam K. Das, Subhas C. Nandy

Published: 2020-06-27T15:18:44.000Z

## 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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2006.15381>)

[PDF](<https://arxiv.org/pdf/2006.15381.pdf>)