| 基于最小生成树的连通支配集求解算法 |
| |
| 引用本文： | 高文宇.基于最小生成树的连通支配集求解算法[J].计算机应用,2009,29(6):1490-1493. |
| |
| 作者姓名： | 高文宇 |
| |
| 作者单位： | 广东商学院,信息学院,广州,510320 |
| |
| 摘 要： | 针对无线网络中的连通支配集(CDS)问题,通过分析得到了CDS的一个重要性质,即简单连通无向图的最小CDS是该图的一棵包含最多叶子节点的生成树中的非叶子节点的集合。根据这个结论,设计了一个新的连通支配集求解算法,实验表明,新算法较前人的算法有更好的性能。
|
| 关 键 词： | 连通支配集 无线传感器网络 生成树算法 connected dominating set Wireless Sensor Network (WSN) spanning tree algorithm |
| 收稿时间： | 2008-12-23 |
| 修稿时间： | 2009-02-24 |
Novel connected dominating set algorithm based on minimum spanning tree |
| |
| GAO Wen-yu.Novel connected dominating set algorithm based on minimum spanning tree[J].journal of Computer Applications,2009,29(6):1490-1493. |
| |
| Authors: | GAO Wen-yu |
| |
| Affiliation: | School of Computer Science;Guangdong University of Business Studies;Guangzhou Guangdong 510320;China |
| |
| Abstract: | Through in-depth analysis, an important property of Connected Dominating Set (CDS) in wireless network was obtained, in which the smallest CDS of a simple connected graph is the non-leaf nodes of a spanning tree with most leaf nodes. A new CDS algorithm was designed on the basis of the analysis. Simulation results show that the algorithm possess better performance than others. |
| |
| Keywords: | |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机应用》浏览原始摘要信息 |
|
点击此处可从《计算机应用》下载全文 |
|
