节点文献

基于禁忌搜索的模拟退火算法在最小控制集中的应用

Application of Simulated Annealing Algorithm Based on Taboo Search in Minimal Dominating Sets

  • 推荐 CAJ下载
  • PDF下载
  • 不支持迅雷等下载工具，请取消加速工具后下载。

【作者】 钟浩； 易勇；

【Author】 ZHONG Hao1,2,YI Yong2(1.School of Mathematics and Computer Engineering,Xihua University,Chengdu 610039,China;2.School of Information Science and Technology,Chengdu University,Chengdu 610106,China)

【机构】 西华大学数学与计算机学院； 成都大学信息科学与技术学院；

【摘要】 图的控制集问题是在给定的简单无向图中求出阶数最小的控制点的集合,目前它已被证明是一个NP-完全问题.针对现阶段已有的模拟退火算法提出了一种改进的基于禁忌搜索的模拟退火算法,并通过与贪心算法、传统模拟退火算法进行比较,证明了该算法可以获得较小的控制集阶数.

【Abstract】 The graph dominating set problem is one about finding the dominating sets with minimal order in a given simple undirected graph,which is known to be NP-complete problem.A simulated annealing algorithm based on taboo search is proposed to improve the present simulated algorithm.Compared with the greedy algorithm and traditional simulated annealing algorithm,this algorithm can get smaller dominating set order.

【关键词】 图； 控制集； 模拟退火； 禁忌搜索； NP-完全；
【Key words】 graph； dominating sets； simulated annealing； taboo search； NP-complete；
【基金】 成都市物流公共信息服务平台建设研究基金(10RKYB041ZF-023)资助项目
  • 【文献出处】 成都大学学报(自然科学版) ,Journal of Chengdu University(Natural Science Edition) , 编辑部邮箱 ,2013年02期
  • 【分类号】TP301.6;O157.5
  • 【被引频次】1
  • 【下载频次】118
打印本页
节点文献中：