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

直径限制最小生成树问题研究

Overview of Bounded- diameter Minimum Spanning Tree Problem
原文传递
导出
摘要 直径限制最小生成树问题是一个经典的网络优化问题。本文对直径限制最小生成树问题进行了综述,介绍了该问题的研究背景、数学模型以及相关的概念,并对问题的求解方法进行了归纳总结。 Bounded -diameter minimum spanning tree problem is a classic combinatorial optimization prob- This paper reviewed the bounded diameter minimum spanning tree problem, at the same time, it introduced the research background mathematical models and concepts and summarized this problem solving algorithm.
作者 姜娜
机构地区 内蒙古大学数学科学学院
出处 《阴山学刊（自然科学版）》 2015年第3期14-16,共3页 Yinshan Academic Journal(Natural Science Edition)
关键词 直径限制 最小生成树 非完全图 BDMST Bounded - diameter Minimum spanning tree Non - complete graph BDMST
分类号 O221.7 [理学—运筹学与控制论]
  • 相关文献

参考文献18

  • 1Gary.Chartrand,PingZhang,著.范益政,汪毅,龚世才,等译.图论导引[M].北京:人民邮电出版社,2007.81-86.
  • 2石磊,冯祖针,杨建强.度、直径约束最小生成树问题及其算法[J].云南民族大学学报（自然科学版）,2012,21(4):295-297. 被引量：2
  • 3Binh. H. T. T, McKay. R. I, Nghia. N. D , etc. New Heuristic and Hybrid Genetic Algorithm for Solving the Bounded Di- ameter Minimum Spanning Tree Problem, in Proceedings of Annual Conference on Genetic and Evolutionary Computation [ J ]. Montreal, 2009,25 (5): 373 - 380.
  • 4Garey M. R, Johnson D. S. Computers and Intractability: a Guide to the Theory of NP - Completeness [ J ]. SIAM Re- view,1982,24( 1 ) : 90 -91.
  • 5Achuthan. N. R, Caccetta L, Caccetta P, etc. Computational Methods for the Diamter Restricted Minimum Weight Span- ning Tree Problem[J]. Australian Journal of Combinatorics, 1994,10 (2) :379 - 384.
  • 6Gouveia. L, Magnanti T. L, Requejo C. A2 - Path Approach for Odd Diameter Constrained Minimum Spanning and Stei- her Trees [ J ]. Networks, 2004,44 (4) :254 - 265.
  • 7Gruber. M , Raidl G. R. A new 0 - 1 ILP Approach for the Bounded Diameter Minimum Spanning Tree Problem, in Pro- ceedings of the Second International Network Optimization Conference [ J ]. Vienna, 2005,15 (3) : 1 - 8.
  • 8Deo. N, abdalla. A. Computing a Diameter - constrained Minimum Spanning Tree in Parallel [ J ] Lecture Notes in Computer Science, 2000,15 ( 4 ) : 17 - 31.
  • 9Julstrom B A. Greedy Heuristic for the Diameter - Con- strained Minimum Spanning Tree Problem [ J ]. Journal of Mathemation Sciences ,2009,161 (6) : 930 - 943.
  • 10Alok Singh Ashok K. Gupta. Improved Heuristics for the Bounded -diameter Minimum Spanning Tree Problem[ J]. Soft Computer,2007,11 (10) : 911 -921.

二级参考文献25

  • 1LiuXikui,LiYan,XuJin.SOLVING MINIMUM SPANNING TREE PROBLEM WITH DNA COMPUTING[J].Journal of Electronics(China),2005,22(2):112-117. 被引量：3
  • 2吴家皋.覆盖多播路由的算法及协议研究综述[J].计算机科学,2007,34(6):7-12. 被引量：4
  • 3AHUJA R K,MAGNANTI T L,ORLIN J B.Network flows:theory,algorithms,and applications(English Version)[M].Beijing:Mechanical Industry Press,2005:510-536.
  • 4DASGUPTA S,PAPADIMITRIOU C H,VAZIRANI U V.Algorithms[EB/OL].http://www.cs.berkeley.edu/-vazirani/algorithms.html.
  • 5SYSLO M M,DEO N,KOWALIK J S.Discrete optimization algorithms:with pascal programs[M].New Jersey:Prentice-Hall,1983:212-236.
  • 6KARGER D R,KLEIN P N,TARJAN R E.A randomized linear-time algorithm to find minimum spanning trees[J].Journal of the ACM,1995,42(2):321-328.
  • 7NEUMANN F,WEGENER I.Randomized local search,evolutionary algorithms,and the minimum spanning tree problem[J].Theoretical Computer Science,2007,378(1):32-40.
  • 8NEUMANN F,WITT C.Ant colony optimization and the minimum spanning tree problem:learning and intelligent optimization[C] //Proc of the 2nd International Conference.Berlin,Heidelberg:Springer-Verlag,2007:153-166.
  • 9Cho J,Breen J.Analysis of the performance of dynamic multicastrouting algorithms[J].Computer Communications,1999,22(7):667-674..
  • 10Flajolet P,Gao Z,Odlyzko A.The distribution of heights of binarytrees and other simple trees[J].Probability and Computing,1992,42:243-248.

共引文献1

阴山学刊（自然科学版）
2015年 第3期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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