摘要
寻找出一个网络图的最小连通支配集有重要实际应用背景,然而如何找到它却是一个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.
出处
《小型微型计算机系统》
CSCD
北大核心
2008年第5期875-878,共4页
Journal of Chinese Computer Systems
基金
国家自然科学基金项目(70471065)资助
上海市重点学科建设项目(T0502)资助
中国工程院重点咨询项目(2006-X-16)资助
关键词
最小连通支配集
极大独立集
启发式算法
minimum connected dominating set
minimal independent set
heuristic algorithm
