欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
寻找出一个网络图的最小连通支配集有重要实际应用背景，然而如何找到它却是一个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.
同期刊论文项目
同项目期刊论文
期刊信息
位置：