Approximation algorithm for the minimum partial connected Roman dominating set problem.

Given a graph G = (V , E) and a function r : V ↦ { 0 , 1 , 2 } , a node v ∈ V is said to be Roman dominated if r (v) = 1 or there exists a node u ∈ N G [ v ] such that r (u) = 2 , where N G [ v ] is the closed neighbor set of v in G. For i ∈ { 0 , 1 , 2 } , denote V r i as the set of nodes with value i under function r. The cost of r is defined to be c (r) = | V r 1 | + 2 | V r 2 | . Given a positive integer Q ≤ | V | , the minimum partial connected Roman dominating set (MinPCRDS) problem is to compute a minimum cost function r such that at least Q nodes in G are Roman dominated and the subgraph of G induced by V r 1 ∪ V r 2 is connected. In this paper, we give a (3 ln | V | + 9) -approximation algorithm for the MinPCRDS problem. [ABSTRACT FROM AUTHOR]