ROMAN DOMINATION AND ITS VARIANTS IN UNIT DISK GRAPHS
Weiping Shang, Xiumei Wang, XIAODONG HU · Discrete Mathematics Algorithms and Applications · 2010
Unit disk graphs are the intersection graphs of equal sized disks in the plane, they are widely used as a mathematical model for wireless ad-hoc networks and some problems in computational geometry. In this paper we first show that Roman dominating set and connected Roman dominating set problems in unit disk graphs are NP-complete, and then present two approximation algorithms for these problems.