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

Efficient Approximation Algorithm for Minimum Connected Dominating Set

作　　者：廖飞雄[1] 马良[1] 范炳全[1] 

机构地区：[1]上海理工大学管理学院,上海200093

出　　处：《小型微型计算机系统》2008年第5期875-878,共4页Journal of Chinese Computer Systems

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

摘　　要：寻找出一个网络图的最小连通支配集有重要实际应用背景,然而如何找到它却是一个NP难题.本文设计了一种简单且高效的近似启发式算法构造网络图的连通支配集,该算法分为三个阶段:首先为顶点分配等级和生成顶点次序表,其次构造一个极大独立集,最后连接极大独立集中顶点.模拟实验表明该算法无论在运行时间和结果上都达到良好的效果.Finding a minimum connected dominating set for a network graph is of great importance in practical applications. However, how to search for it exactly is a NP-hard problem. This paper proposes a simple but efficient approximation heuristic algorithm for constructing a connected dominating set, which includes three stages, firstly assigning a rank for each node and forming an ordered list, then constructing a minimal independent set（MIS）, and at last connecting the nodes in the MIS. Simulation experiments show the high efficiency of this algorithm in both execution time and results.

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]