最小连通支配集问题的化简算法

摘要

By analyzing the dominant constraints and connectivity constraints of connected dominating set, two reduction rules for minimum connected dominating set in simple connected graph is proposed. These rules can find out some required nodes and delete some redundant nodes in advance through classification of neighbors of any node, and through finding cut nodes in graph, thus reducing the size of the original problem.These reduction rules are proved theoretically and tested by random simulations.%分析连通支配集的支配性约束和连通性约束条件,提出2条针对简单无向连通图最小连通支配集问题的化简规则.规则通过对图中节点的邻节点进行分类以及寻找图的割点提前确定一些必选节点,同时删除一些多余节点,从而降低原问题的规模.从理论上证明了化简规则的正确性,并通过随机仿真实验验证化简规则的有效性.