.png){kind=icon}
返回
Approximation algorithm for connected Roman k-dominating set
.png){kind=icon}
PRE
AI
DOI：10.1016/j.jcss.2026.103773.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
设k（k ≥ 2）为正整数，G为简单图，其顶点集为V(G)。G上的罗马k-支配函数（Rk-DF）f(kR): V(G) → {0, 1, 2}满足：对于每个满足f(kR)(u) = 0的顶点u，至少存在k个相邻顶点v(1), v(2),..., v(k)，使得f(kR)(v(i)) = 2（i = 1, 2, ..., k）。最小罗马k-支配集问题旨在计算一个总权重∑_{v ∈ V} f(kR)(v)最小的罗马k-支配函数f(kR)。最小连通罗马k-支配集问题（MinCRkDS）寻求找到一个最小权重的罗马k-支配函数f(kR)，使得由D-kR = {v ∈ V | f(kR)(v) = 1或f(kR)(v) = 2}诱导的G的子图是连通的。据我们所知，本文是首次在一般图中解决MinCRkDS问题的论文。我们为MinCRkDS问题提出了一种贪心算法，其近似比为(1 + ε)(2 + ln(k + 1 + 2Δ))（对于任意ε > 0），其中Δ是图的最大度。（c）2026 Elsevier Inc. 版权所有，包括文本和数据挖掘、AI训练及类似技术的权利。
Keyword:
Roman k-dominating set
Connected Roman k-dominating set
Greedy algorithm
Non-submodular
Approximation ratio
期刊
J
IF:
0.9
论文数:
56
被引数:
4.5K
机构
查看更多机构
引用论文
Approximation algorithm for a generalized Roman domination problem in unit ball graphs单位球图中的广义罗马占据问题的近似算法
.png){kind=icon}
PREAI
分享收藏分享收藏分享收藏
没有更多内容