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

度、直径约束最小生成树问题及其算法 被引量：2

Degree-Constrained and Diameter-Constrained Minimum Spanning Tree Problem and Its Algorithm
下载PDF
导出
摘要 提出了度、直径约束最小生成树问题,证明了该问题是NP-完全的.建立了该问题的数学规划模型.给出了启发式求解算法,其时间复杂性为O(mn).分析和实例实验表明,该算法有良好的效果. The degree -constrained and diameter- constrained minimum spanning tree problem was discussed, which proved to be NP- Complete. A mathematical programming model of the problem was proposed. A heuristic algorithm was proposed to solve this problem, whose time complexity was 0 （mn）. The algorithm was proved to be effective through analysis and experiments.
作者 石磊 冯祖针 杨建强
机构地区 红河学院数学学院
出处 《云南民族大学学报（自然科学版）》 CAS 2012年第4期295-297,共3页 Journal of Yunnan Minzu University:Natural Sciences Edition
基金 国家自然科学基金(11161020) 红河学院硕博基金(10BSS136)
关键词 最小生成树 启发式算法 度约束 直径约束 minimum spanning tree heuristic algorithm degree - constrained diameter - constrained
分类号 O157.6 [理学—基础数学]
  • 相关文献

参考文献9

  • 1AHUJA R K,MAGNANTI T L,ORLIN J B. Network flows:Theory,algorithms,and applications[M].Beijing:Mechanical-Industry Press,2005.
  • 2NARULA S C,HO C A. Degree-constrained minimum spanning tree[J].Computers and Operations Research,1980,(04):239-249.
  • 3TORKESTANI J A. Degree-constrained minimum spanning tree problem in stochastic graph[J].Cybernetics and Systems,2012,(01):1-21.
  • 4JULSTROM B A. Greedy heuristics for the bounded diameter minimum spanning tree problem[J].Journal of Experimental Algorithmics(JEA),2009,(01):1-14.
  • 5LUCENA A,RIBEIRO C C,SANTOS A C. A hybrid heuristic for the diameter constrained minimum spanning tree problem[J].Journal of Global Optimization,2010,(03):363-381.
  • 6GAREY M R,JOHNSON D S. Computers and intractability:A guide to the theory of NP-completeness[M].San Francisco:WH Freeman & Co,1979.206-218.
  • 7吴家皋.覆盖多播路由的算法及协议研究综述[J].计算机科学,2007,34(6):7-12. 被引量：4
  • 8PAPADIMITRIOU C H. Computational complexity[M].Boston:Addison-Wesley,2004.
  • 9BINH H T T;HOAI N X;MCKAY R I.A new hybrid genetic algorithm for solving the bounded diameter minimum spanning tree problem[A]香港,20083128-3134.

二级参考文献30

  • 1吴家皋,叶晓国,姜爱全.一种异构环境下覆盖多播网络路由算法[J].软件学报,2005,16(6):1112-1119. 被引量：12
  • 2Diot C,Levine BN,Lyles B,et al.Deployment Issues for the IP Multicast Service and Architecture[J].IEEE Network,2000,14(1):78～88
  • 3El-Sayed A,Roca V.A Survey of Proposals for an Alternative Group Communication Service[J].IEEE Network,Jan/Feb 2003.2～7
  • 4Banerjee S,Bhattacharjee B.A Comparative Study of Application Layer Multicast Protocols[A].In:submitted for review,2002
  • 5Hassin R,Tamir A.On the minimum diameter spanning tree problem[J].Inform Processing Lett,1995,53:109～111
  • 6Wang Z,Crowcroft J.QoS Routing for Supporting Resource Reservation[J].IEEE Journal on Selected Areas in Communications,1996,14(7):1228～1234
  • 7Salama H F,Reeves D S,Viniotis Y.The Delay-constrained Minimum Spanning Tree Problem[A].In:Proceedings of the International Symposium on Computers and Communications (ISCC'97)[C],June 1997
  • 8Garg N,Khandekar R,Kunal K,et al.Bandwidth Maximization in Multicasting.In:Proceedings of the 11th Annual European Symposium on Algorithms,September 2003.242～253
  • 9Banerjee S,Kommareddy C,Kar K,et al.Construction of an Efficient Overlay Multicast Infrastructure for Real-time Applications[A].In:Proceedings of the IEEE INFOCOM[C].San Franciso,2002.1521～1531
  • 10Shi S,Turner J.Multicast Routing and Bandwidth Dimensioning in overlay networks[J].IEEE Journal on Selected Areas in Communications,2002,20(8):1444～1455

共引文献3

同被引文献21

  • 1FURER M,RAGHAVACHARI B. An NC approximation algo- rithm for the minimum degree spanning tree problem[C]// Proceedings of the 28th Annual Alleton Conference on Com- munication, Control and Computing. 1990:274 - 281.
  • 2FURER M, RAGHAVACHARI B. Approximating the min- imum degree spanning tree to within one from optimal de- gree[ C]// ACM -SIAM Symposium on Discrete Algo- rithms. 1992:317 - 324.
  • 3BLIN L, BUTELLE F. The first approximated distributed algorithm for the minimum degree spanning tree problem on general graphs [ J ]. Computer Society, 2004,15 (03) : 507 -516.
  • 4HOCHBAUM D. Approximation algorithms for NP- hard problems[ M]. International Thomson Publishing Compa- ny, 1998.
  • 5Gary.Chartrand,PingZhang,著.范益政,汪毅,龚世才,等译.图论导引[M].北京:人民邮电出版社,2007.81-86.
  • 6Binh. 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.
  • 7Garey 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.
  • 8Achuthan. 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.
  • 9Gouveia. 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.
  • 10Gruber. 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.

引证文献2

云南民族大学学报（自然科学版）
2012年 第4期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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