{"id":"arxiv/2607.14467","url":"https://arxiv.org/abs/2607.14467","tags":["cs.DS","cs.DM","math.CO"],"score":0,"title":"Semitotal domination in unit disk graphs","domain":"cs.DS","source":"arxiv","authors":["Mingjun Liu","Weiping Shang"],"reviews":0,"subject":"cs.DS","summary":"A set $S \\subseteq V$ is called a {\\em semitotal dominating set} of $G=(V,E)$ if every vertex in $V \\setminus S$ is adjacent to at least one vertex in $S$, and every vertex in $S$ is within distance 2 of another vertex in $S$. The corresponding decision problem is NP-complete even for unit disk graphs. In this paper, we present a 5-factor approximation algorithm for the Minimum Semitotal Domination problem on unit disk graphs in the graph-based input model. The algorithm processes the layers of a Breadth-First-Search tree and constructs a maximal independent set whose vertices satisfy the…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-16","reactions":{}}