LAUSR

In this paper we propose a generalized Roman domination problem called connected strong k -Roman dominating set problem. It is NP-hard even in a unit ball graph. Unit ball graphs are the intersection graphs of equal sized balls in the three-dimensional space, they are widely used as a mathematical model for wireless sensor networks and some problems in computational geometry. This paper presents the first constant approximation algorithm with a guaranteed performance ratio at most $$6(k+2)$$ 6 ( k + 2 ) in unit ball graphs, where k is a positive integer.