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

Reduction Algorithm for Minimum Connected Dominating Set Problem

作　　者：高文宇[1] 

机构地区：[1]广东商学院信息学院,广州510320

出　　处：《计算机工程》2011年第10期55-57,共3页Computer Engineering

基　　金：广东省自然科学基金资助项目(8151032001000013)

摘　　要：分析连通支配集的支配性约束和连通性约束条件,提出2条针对简单无向连通图最小连通支配集问题的化简规则。规则通过对图中节点的邻节点进行分类以及寻找图的割点提前确定一些必选节点,同时删除一些多余节点,从而降低原问题的规模。从理论上证明了化简规则的正确性,并通过随机仿真实验验证化简规则的有效性。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.

关 键 词：最小连通支配集 化简 参数算法 复杂性 

分 类 号：TP311.52[自动化与计算机技术—计算机软件与理论]