文献类型：期刊文献

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

英文题名：Design and Analysis of Greedy Algorithm the Deformation-positive Influence Dominating Set in Gragh

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

第一作者：张涛

机构：[1]新乡学院网络管理中心;[2]新乡学院计算机与信息工程学院

第一机构：新乡学院

年份：2015

卷号：0

期号：2

起止页码：169-172

中文期刊名：河南师范大学学报：自然科学版

收录：CSTPCD;;北大核心:【北大核心2014】；

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

语种：中文

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

外文关键词：wireless sensor network; graph; dominating set; greedy algorithm; performance ratio

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