Approximation algorithm for connected Roman k-dominating set

He, Mengmeng

doi:10.1016/j.jcss.2026.103773

Approximation algorithm for connected Roman k-dominating set

2026-02-01

0

PRE

AI

DOI：10.1016/j.jcss.2026.103773

Original

Original request for help

Save

Abstract

En 中文

Let k (k >= 2) be a positive integer, and let G be a simple graph with the vertex set V (G). A Roman k-dominating function (Rk-DF) on G is a function f(kR): V (G) -> {0, 1,2} such that every vertex u with f(kR)(u) = 0 is adjacent to at least k vertices v(1), v(2),..., v(k) with f(kR)(v(i)) = 2 for i = 1, 2, ... , k. The minimum Roman k-dominating set problem aims to compute a Roman k-dominating function f(kR) that minimizes the total weight & sum;v is an element of V f(kR)(v). The minimum Connected Roman k-dominating set problem (MinCRkDS) seeks to find a minimum-weight Roman k-dominating function f(kR) such that the subgraph of G induced by D-kR = {v is an element of V | f(kR)(v) = 1 or f(kR)(v) = 2} is connected. As far as we know, this paper is the first paper to solve MinCRkDS in general graphs. We present a greedy algorithm for MinCRkDS with an approximation ratio (1 + epsilon)(2 + ln(k + 1 + 2 Delta)) for any epsilon >0, where Delta is the maximum degree of the graph. (c) 2026 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

Keywords:

Roman k-dominating set

Connected Roman k-dominating set

Greedy algorithm

Non-submodular

Approximation ratio

Approximation algorithm for connected Roman k-dominating set

Abstract

Journal

Organization