Consider a graph with nonnegative node weight. A vertex subset is called a CDS (connected dominating set) if every other node has at least one neighbor in the subset and the subset induces a connected subgraph. Furthermore, if every other node has at least $m$ neighbors in the subset, then the node subset is called a $(1,m)$CDS. The minimum-weight $(1,m)$CDS problem aims at finding a $(1,m)$CDS with minimum total node weight. In this paper, we present a new polynomial-time approximation algorithm for this problem with approximation ratio $2H(\delta_{\max}+m-1)$, where $\delta_{\max}$ is the maximum degree of the given graph and $H(\cdot)$ is the Harmonic function, i.e., $H(k)=\sum_{i=1}^k \frac{1}{i}$.
翻译：考虑一个非负节点重量的图形。 如果每个其他节点在子集中至少有一个相邻方, 则顶点子子集称为 CDS (相连接的顶点集) 。 此外, 如果每个其他节点在子集中至少有一个相邻方$, 那么结点子集就被称为$(1, m) $ CDS。 最小重量$(1, m) $ CDS 问题旨在找到一个 $(1, m) $ CDS, 且总结点重量最小。 在本文中, 我们为此问题提出了一个新的多盘点位时近似算法 $ 2H (\ delta\\\\\\\\ max\\ max} $, 其中$\ delta\\ max} 是给定图形的最大程度, $H (\\ ) $ (cdot) 是调理函数, 即 $H (k) sumi=1\\\\\\\\\\\\\\\\\\\\\\\\\ i}美元。
相关内容
微信扫码咨询专知VIP会员