图的正面影响控制集中贪婪算法的设计与分析  

Design and Analysis of Greedy Algorithm the Deformation-positive Influence Dominating Set in Gragh

作　　者：张涛[1] 朱莉娟[2] 

机构地区：[1]新乡学院网络管理中心,河南新乡453003 [2]新乡学院计算机与信息工程学院,河南新乡453003

出　　处：《河南师范大学学报（自然科学版）》2015年第2期169-172,共4页Journal of Henan Normal University(Natural Science Edition)

基　　金：河南省重点科技攻关项目(092102210149)

摘　　要：对于没有固定基础设施的无线传感器网络,设计一个优良合理的拓扑控制协议是关键.根据图的控制集在无线传感器网络组建虚拟骨干网的应用,研究了图上控制集问题的一个变形—正面影响控制集问题.针对图中是否存在孤立顶点,分两种情形讨论,设计了相应的贪婪算法,并分析了算法的性能比.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.

关 键 词：无线传感器网络 图 控制集 贪婪算法 性能比 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]