ﻻ يوجد ملخص باللغة العربية
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.
Retraction note: After posting the manuscript on arXiv, we were informed by Erik Jan van Leeuwen that both results were known and they appeared in his thesis[vL09]. A PTAS for MDS is at Theorem 6.3.21 on page 79 and A PTAS for MCDS is at Theorem 6.3.
We recently introduced the graph invariant twin-width, and showed that first-order model checking can be solved in time $f(d,k)n$ for $n$-vertex graphs given with a witness that the twin-width is at most $d$, called $d$-contraction sequence or $d$-se
Let $G=(V,E)$ be an undirected graph. We call $D_t subseteq V$ as a total dominating set (TDS) of $G$ if each vertex $v in V$ has a dominator in $D$ other than itself. Here we consider the TDS problem in unit disk graphs, where the objective is to fi
A bipartite graph $G=(A,B,E)$ is ${cal H}$-convex, for some family of graphs ${cal H}$, if there exists a graph $Hin {cal H}$ with $V(H)=A$ such that the set of neighbours in $A$ of each $bin B$ induces a connected subgraph of $H$. Many $mathsf{NP}$-