| 一种求解最小连通支配集的高效近似算法 |
| |
| 引用本文： | 廖飞雄,马良,范炳全. 一种求解最小连通支配集的高效近似算法[J]. 小型微型计算机系统, 2008, 29(5): 875-878 |
| |
| 作者姓名： | 廖飞雄 马良 范炳全 |
| |
| 作者单位： | 上海理工大学,管理学院,上海,200093 |
| |
| 基金项目： | 国家自然科学基金 , 上海市重点学科建设项目 , 中国工程院重点咨询项目 |
| |
| 摘 要： | 寻找出一个网络图的最小连通支配集有重要实际应用背景,然而如何找到它却是一个NP难题.本文设计了一种简单且高效的近似启发式算法构造网络图的连通支配集,该算法分为三个阶段:首先为顶点分配等级和生成顶点次序表,其次构造一个极大独立集,最后连接极大独立集中顶点.模拟实验表明该算法无论在运行时间和结果上都达到良好的效果.
|
| 关 键 词： | 最小连通支配集 极大独立集 启发式算法 求解 最小连通支配集 近似算法 Dominating Set Minimum Approximation Algorithm 效果 结果 运行时间 模拟实验 后连接 极大独立集 算法构造 顶点次序 分配 启发式 设计 背景 应用 网络图 |
| 文章编号： | 1000-1220(2008)05-0875-04 |
| 修稿时间： | 2007-04-09 |
Efficient Approximation Algorithm for Minimum Connected Dominating Set |
| |
| LIAO Fei-xiong,MA Liang,FAN Bing-quan. Efficient Approximation Algorithm for Minimum Connected Dominating Set[J]. Mini-micro Systems, 2008, 29(5): 875-878 |
| |
| Authors: | LIAO Fei-xiong MA Liang FAN Bing-quan |
| |
| Affiliation: | LIAO Fei-xiong,MA Liang,FAN Bing-quan (College of Management,University of Shanghai for Science , Technology,Shanghai 200093,China) |
| |
| Abstract: | 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 h... |
| |
| Keywords: | minimum connected dominating set minimal independent set heuristic algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
