# Total Domination in Unit Disk Graphs

Source: [Total Domination in Unit Disk Graphs](<https://www.sota2.com/research/paper/68fa680d1e209131cea19db7>)

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

Data updated: 2025-10-27T06:03:45.482Z

Authors: Sangram K. Jena, Gautam K. Das

Published: 2020-07-23T13:11:19.000Z

## Abstract

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 find a minimum cardinality total dominating set for an input graph. We prove that the TDS problem is NP-hard in unit disk graphs. Next, we propose an 8-factor approximation algorithm for the problem. The running time of the proposed approximation algorithm is $O(n \\log k)$, where $n$ is the number of vertices of the input graph and $k$ is output size. We also show that TDS problem admits a PTAS in unit disk graphs.

## 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/2007.11997>)

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