works on
approximation algorithms 1computational complexity 1domination problems 1graph algorithms 1unit disk graphs 1

From the 1 of 1 linked paper with an AI index.

collaborators
Showing cs.DSShow all

1 paper · 1 filter

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…