Approximation algorithm for the minimum partial connected Roman dominating set problem

期刊论文
发表日期：

2024年4月26日

查看全文

Yaoyao Zhang,
Zhao Zhang,
Ding-Zhu Du

摘要

Given a graph $G=(V,E)$ $G = (V, E)$ and a function $r:V\mapsto \{0,1,2\}$ $r : V \mapsto {0, 1, 2}$ , a node $v\in V$ $v \in V$ is said to be Roman dominated if $r(v)=1$ $r (v) = 1$ or there exists a node $u\in N_G[v]$ $u \in N_{G} [v]$ such that $r(u)=2$ $r (u) = 2$ , where $ N_G[v]$ $N_{G} [v]$ is the closed neighbor set of v in G. For $i\in \{0,1,2\}$ $i \in {0, 1, 2}$ , denote $V_r^i$ $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|$ $c (r) = | V_{r}^{1} | + 2 | V_{r}^{2} |$ . Given a positive integer $Q\le |V|$ $Q \leq | 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\cup V_r^2$ $V_{r}^{1} \cup V_{r}^{2}$ is connected. In this paper, we give a $(3\ln |V|+9)$ $(3 ln | V | + 9)$ -approximation algorithm for the MinPCRDS problem.