期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

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

Application of Simulated Annealing Algorithm Based on Taboo Search in Minimal Dominating Sets
下载PDF
导出
摘要 图的控制集问题是在给定的简单无向图中求出阶数最小的控制点的集合,目前它已被证明是一个NP-完全问题.针对现阶段已有的模拟退火算法提出了一种改进的基于禁忌搜索的模拟退火算法,并通过与贪心算法、传统模拟退火算法进行比较,证明了该算法可以获得较小的控制集阶数. 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 N-P-complete problem.A simulated annealing algo- rithm 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.
作者 钟浩 易勇
机构地区 西华大学数学与计算机学院 成都大学信息科学与技术学院
出处 《成都大学学报（自然科学版）》 2013年第2期138-141,共4页 Journal of Chengdu University（Natural Science Edition）
基金 成都市物流公共信息服务平台建设研究基金(10RKYB041ZF-023)资助项目
关键词 图 控制集 模拟退火 禁忌搜索 NP-完全 graph dominating sets simulated annealing taboo search NP-eomplete
分类号 TP301.6 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献15

  • 1Bertolo R,Ostergard P R J,Weakley W D.An updated table ofbinary/ternary mixed covering codes[J].Journal of CombinatorialDesign,2004,12(3):157-176.
  • 2Wu J,Cardei M,Dai F,et al.Extended dominating set and itsapplications in ad hoc networks using cooperative communication[J].IEEE Transactions on Parallel and Distributed Systems,2006,17(8):851-864.
  • 3Stojmenovic I,Seddigh M,Zunic J.Dominating set and neighboreliminationbased broadcasting algorithms in wireless networks[J].IEEE Tramsactions on paralell and distributed systems,2002,13(1):14-25.
  • 4Garey M R,Johnson D S.Computers and intractability:a guideto the theory of NP-completeness[M].San Francisco:WH Free-man&Co.,1979.
  • 5Wille L T.Thefootball pool problemfor 6 matches:a new upperbound obtained by simulated annealing[J].Journal of Combina-tiorial Combin Theory(Series A),1987,45(2):171-177.
  • 6Pruchnewski A.On the domination number of a graph[J].Dis-crete Mathematics,2002,251(1-3):129-136.
  • 7陈卫东,孟小华.求图控制集问题的模拟退火算法的改进[J].重庆师范大学学报（自然科学版）,2004,21(2):24-27. 被引量：3
  • 8Kann V.On the Approximability of NP-complete optimizationproblems[D].Stockholm:Royal Institute ofTechnology,1992.
  • 9Guha S,Khuller S.Approximation algorithmsfor connected domi-nating sets[J].Algorithmica,1998,20(4):374-387.
  • 10Davies R,Royle G F.Graph domination,tabu search and thefootball pool problem[J].Discrete Applied Mathematics,1997,74(2):217-228.

二级参考文献9

  • 1GAREV M R,JOHNSON D S. Computers and Intractability: A Guide to the Theory of NP-Completeness [ M ]. San Francisco: Freeman, 1979.
  • 2WILLE L T. The Football Pool Problem for 6 Matches: a New Upper Bound Obtained by Simulated Annealing[ J]. J Combin Theory Ser, A 1987,45(2): 171-177.
  • 3VAN LAARHOVEN P J M. Theoretical and Computational Aspects of Simulated Annealing [ J ]. Centrum voor Wiskunde en Informatica Tract, 1988,57.
  • 4DAVIES R, GORDON F R. Graph Domination, Tabu Search and the Football Pool Problem [ J ]. Discrete Applied Mathematics, 1997,74 ( 3 ) :217-228.
  • 5LIANG Y D. Parallel Algorithms for the Domination Problems in Trapezoid Graphs [ J ]. Discrete Appl Math, 1997,74 ( 3 ): 241-249.
  • 6ALBER J, BODLAENDER H L, FERNAU H,et al. Fixed Parameter Algorithms for DOMINATING SET and Related Problems on Planar Graphs [ J ] . Algorithmica, 2002,33(4) :461-493.
  • 7PRUCHNEWSKI A. On the domination number of a graph [J]. Discrete Mathematics ,2002,251: 129-136.
  • 8康立山 谢云 尤矢勇.非数值并行算法(第一册),模拟退火算法[M].北京:科学出版社,1998..
  • 9毛经中,刘慧清,王春香.k×n格图P_k×P_n的控制数[J].应用数学,2001,14(1):1-7. 被引量：3

共引文献35

同被引文献19

  • 1陈卫东,孟小华.求图控制集问题的模拟退火算法的改进[J].重庆师范大学学报（自然科学版）,2004,21(2):24-27. 被引量：3
  • 2Zhong Hao, Yi Yong. Application of simulated annealing algorithmbased on taboo search in minimal dominating sets. Journal of ChengduUniversity(Natural Science Edition) ,2013 ;32(2) :138-141.
  • 3Bertolo R,Ostergird P R J, Weakley W D. An updated table of bina-ry/ternary mixed covering codes . Journal of Combinatorial Designs,2004;12(3) :157-176.
  • 4Wu J, Cardei M, Dai F,et al. Extended dominating set and its ap-plications in ad hoc networks using cooperative communication. IEEETransactions on Parallel and Distributed System, 2006 ; 17 ( 8 ):851-864.
  • 5Garey M R, Johnson D S. Computers and intractability: a guide tothe theory of NP-compieteness. USA.: W. H. Freeman and Company,1979:53-56.
  • 6Pruchnewski A. On the domination number of a graph. DiscreteMathematics,2002;251(1-3) : 129-136.
  • 7Ebrahimi B J, Jahanbakht N, Mahmoodian E S. Vertex domination ofgeneralized Petersen graphs. Discrete Mathematics, 2009; 309 ( 13 ):4355-4361.
  • 8Guha S, Khuller S. Approximation algorithms for connected domina-ting sets. Algorithmica, 1998 ;20(4) :374-387.
  • 9Parekh A K. Analysis of a greedy heuristic for finding small domina-ting sets in graphs. Information Processing Letters, 1991; 39 (5 ):237-240.
  • 10Wille L T. The football pool problem for 6 matches : a new upperbound obtained by simulated annealing. Journal of Combinatorial The-ory, Series A,1987;45(2) -171-177.

引证文献1

二级引证文献1

成都大学学报（自然科学版）
2013年 第2期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部