approximation algorithms 1computational complexity 1domination problems 1graph algorithms 1unit disk graphs 1
From the 1 of 2 linked papers with an AI index.
2 papers
cs.DS2026
Semitotal domination in unit disk graphs
Mingjun Liu, Weiping Shang
The paper studies the Minimum Semitotal Domination problem on unit disk graphs, proving it is NP‑complete and presenting a linear‑time 5‑approximation algorithm based on BFS layers…
math.CO2026
Double Italian domination in trees
Weiping Shang, Shanshan Zhang
Let be a graph with vertex set . A double Roman dominating function on a graph is a function satisfying the conditions that if , t…