论文标题
在图中的多项式时间近似与最小主导集
A polynomial-time approximation to a minimum dominating set in a graph
论文作者
论文摘要
图$ g =（v，e）$的一个{\ em占主导地位}是顶点$ s \ subseteq v $的子集，使得每个顶点$ v \ in V \ setMinus s $中的每个顶点$ v \至少在$ s $中具有一个邻居。在连接图中找到具有最小基数的主导设置$ g =（v，e）$是NP-HARD。此处描述的此问题的多项式时间近似算法在两个阶段起作用。在第一阶段，由贪婪的算法产生了主导集，在第二阶段，该主导集被纯化（还原）。减少是通过对第一阶段算法流程的分析以及在第一阶段生成的主导集的特殊聚类来实现的。主导套装的聚类自然会导致一种特殊的图形$ g $的森林，这是第二净化阶段的基础。我们揭示了某些类型的图形，当总体算法构建最佳解决方案时，第一阶段的算法已经提供了最佳解决方案并得出足够的条件。我们给出了第一阶段算法的三个替代近似值，其中两个以仅不变的问题实例参数表示，并且我们还为整个两阶段算法提供了一个额外的近似值。事实证明，第一阶段的贪婪算法与固定盖的早期已知的最先进算法和主导的设定问题chvátal\ cite {chvatal}和parekh \ cite {parekh}基本相同。在实践中，第二个纯化阶段导致在第一阶段创建的主要集合大大降低。两个阶段的实际行为均已验证，以随机生成的问题实例。计算实验强调了第1阶段的解决方案与第2阶段解决方案之间的差距。
A {\em dominating set} of a graph $G=(V,E)$ is a subset of vertices $S\subseteq V$ such that every vertex $v\in V\setminus S$ has at least one neighbor in $S$. Finding a dominating set with the minimum cardinality in a connected graph $G=(V,E)$ is known to be NP-hard. A polynomial-time approximation algorithm for this problem, described here, works in two stages. At the first stage a dominant set is generated by a greedy algorithm, and at the second stage this dominating set is purified (reduced). The reduction is achieved by the analysis of the flowchart of the algorithm of the first stage and a special kind of clustering of the dominating set generated at the first stage. The clustering of the dominating set naturally leads to a special kind of a spanning forest of graph $G$, which serves as a basis for the second purification stage. We expose some types of graphs for which the algorithm of the first stage already delivers an optimal solution and derive sufficient conditions when the overall algorithm constructs an optimal solution. We give three alternative approximation ratios for the algorithm of the first stage, two of which are expressed in terms of solely invariant problem instance parameters, and we also give one additional approximation ratio for the overall two-stage algorithm. The greedy algorithm of the first stage turned out to be essentially the same as the earlier known state-of-the-art algorithms for the set cover and dominating set problem Chvátal \cite{chvatal} and Parekh \cite{parekh}. The second purification stage results in a significant reduction of the dominant set created at the first stage, in practice. The practical behavior of both stages was verified for randomly generated problem instances. The computational experiments emphasize the gap between a solution of Stage 1 and a solution of Stage 2.
