论文标题
在放松占主导地位的方面
On Relaxation of Dominant Sets
论文作者
论文摘要
在图$ g =（v，e）$中，k式套装$ s $是所有顶点$ v $ \ $ s $最多均为$ k $ v $ s $的$ s $。找到最小的k条套件与最小主导设置问题和最大独立集问题本质上相关，这些问题已在图理论中进行了广泛研究。本文介绍了第一种已知的算法，该算法与已知的最低主导算法相结合，仅在额外的多项式时间成本中与最低主导集相比，以求解所有K条设置问题。该算法进一步成功以$（α，α-1）$统治集成功，其中$α> 1 $，对于在s $中的顶点v $ \的接近性上存在约束。相反，该辅助应用程序与最大独立集算法结合使用。
In a graph $G = (V,E)$, a k-ruling set $S$ is one in which all vertices $V$ \ $S$ are at most $k$ distance from $S$. Finding a minimum k-ruling set is intrinsically linked to the minimum dominating set problem and maximal independent set problem, which have been extensively studied in graph theory. This paper presents the first known algorithm for solving all k-ruling set problems in conjunction with known minimum dominating set algorithms at only additional polynomial time cost compared to a minimum dominating set. The algorithm further succeeds for $(α, α- 1)$ ruling sets in which $α> 1$, for which constraints exist on the proximity of vertices v $\in S$. This secondary application instead works in conjunction with maximal independent set algorithms.
