| 图的正面影响控制集中贪婪算法的设计与分析 |
| |
| 引用本文： | 张涛,朱莉娟.图的正面影响控制集中贪婪算法的设计与分析[J].河南师范大学学报(自然科学版),2015(2):169-172. |
| |
| 作者姓名： | 张涛 朱莉娟 |
| |
| 作者单位： | 新乡学院网络管理中心;新乡学院计算机与信息工程学院 |
| |
| 基金项目： | 河南省重点科技攻关项目(092102210149) |
| |
| 摘 要： | 对于没有固定基础设施的无线传感器网络,设计一个优良合理的拓扑控制协议是关键.根据图的控制集在无线传感器网络组建虚拟骨干网的应用,研究了图上控制集问题的一个变形—正面影响控制集问题.针对图中是否存在孤立顶点,分两种情形讨论,设计了相应的贪婪算法,并分析了算法的性能比.
|
| 关 键 词： | 无线传感器网络 图 控制集 贪婪算法 性能比 |
Design and Analysis of Greedy Algorithm the Deformation-positive Influence Dominating Set in Gragh |
| |
| ZHANG Tao;ZHU Lijuan.Design and Analysis of Greedy Algorithm the Deformation-positive Influence Dominating Set in Gragh[J].Journal of Henan Normal University(Natural Science),2015(2):169-172. |
| |
| Authors: | ZHANG Tao;ZHU Lijuan |
| |
| Institution: | ZHANG Tao;ZHU Lijuan;Department of Network Management Center,Xinxiang university;College of Computer and Information Engineering,Xinxiang university; |
| |
| Abstract: | It is necessary to design good and reasonable topology protocol to prolong the lifetime of sensor nodes and the whole network.According to the chart control set in the application of wireless sensor network to form a virtual backbone network,we studies positive influence dominating set problem in graph,which is a variant of dominating set problem in graph.We divide the problem into two cases according to whether there are isolated vertices in graph,then design greedy algorithms and analyze performance ratios respectively. |
| |
| Keywords: | wireless sensor network graph dominating set greedy algorithm performance ratio |
| 本文献已被 CNKI 等数据库收录！ |
