一种求解最小连通支配集的高效近似算法

摘要：

寻找出一个网络图的最小连通支配集有重要实际应用背景,然而如何找到它却是一个NP难题.本文设计了一种简单且高效的近似启发式算法构造网络图的连通支配集,该算法分为三个阶段:首先为顶点分配等级和生成顶点次序表,其次构造一个极大独立集,最后连接极大独立集中顶点.模拟实验表明该算法无论在运行时间和结果上都达到良好的效果.

关键词：最小连通支配集、极大独立集、启发式算法

所属期刊栏目：29

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金项目70471065;上海市重点学科建设项目T0502;中国工程院重点咨询项目2006-X-16

在线出版日期：2008-07-09（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：875-878