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

求解满瓶颈Steiner树 被引量：1

On Full Bottleneck Steiner Tree Problem
下载PDF
导出
摘要 首先对Steiner树,瓶颈Steiner树研究现状加以介绍,指出满瓶颈Steiner树就是在已知图中找一颗树S,使给定的点集在S中的点都为叶子,且最大的边权值最小,然后给出满瓶颈Steiner树的定义,利用分解,转化,组合的思想,给出求解满瓶颈Steiner树问题的一个多项式算法,证明算法正确性,说明该算法的时间复杂性,最后给出相应的数值例子,说明算法正确性. It is suggested to solve the full bottleneck Steiner tree problem is to find a tree S from the undirected graph G, with all the vertices in the given points being leaves and the weights of the maximum edges being minimum. After giving out the definition of full bottleneck Steiner tree, we use methed of transforming, decomposing and combining to give out a polynominal algorithm for solving the problem. Complexity of time in that algorithm is given, and examples are presented to show the validity of the algorithm.
作者 康妮妮 唐恒永
机构地区 沈阳师范大学数学与系统科学学院
出处 《沈阳师范大学学报（自然科学版）》 CAS 2008年第1期7-9,共3页 Journal of Shenyang Normal University:Natural Science Edition
基金 国家自然科学基金资助项目(10471096)
关键词 满瓶颈Steiner树 最小支撑树 多项式算法 时间复杂性 full bottleneck Steiner tree minimum spanning tree polynomial algorithm complexity of time
分类号 O221.7 [理学—运筹学与控制论] O115.7 [理学—基础数学]
  • 相关文献

参考文献11

  • 1KARP R.Reducibility among combinatorial problems[C].Complexity Compute Computations,1972:85-103.
  • 2GAREY M,GRAHAM R,GOHNSON D.The complexity of computing Steiner minimal trees[J].SIAM Journal on Applied Mathematics,1977,32(4):835-859.
  • 3GAREY M,GOHNSON D.The rectilinear Steiner problem is NP-complete[J].SIAM Journal on Applied Mathematics,1977,32(4):826-834.
  • 4ROBINS G,ZELIKOYSKY A.Improved Steiner tree approximation in graphs[J].Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms,2000:770-779.
  • 5LU C L,TANG C Y.The full Steiner tree problem[J].Theoretical Computer Science,2003,306(3):55-67.
  • 6FUCHS B.A note on the terminal Steiner tree problem[J].Information Processing Letters,2003,87(4):219-220.
  • 7GUO Huilin,GUO Liang-xue.On the terminal Steiner tree problem[J].Information Processing Letters,2002,84(2):103-107.
  • 8CHIANG C,MAJID S,WONG C.Global Routing Based on Steiner Min-Max Trees[J].IEEE Transaction Computer-Aided Design,1990,9(12):1318-1325.
  • 9MARTINEZ F,PINA J,SOARES J.Algorithms for terminal Steiner trees[C].ProNEx project,2005:369-379.
  • 10LU C L,TANG C Y,LEE R.The full Steiner tree problem[J].Theoretical Computer Science,2003,306(3):55-67.

同被引文献7

  • 1HEUBERGER C. Inverse optimization, a survey on problems, methods, and result[J]. Comb Optim, 2004,8(33) : 329- 361.
  • 2CAMERIN P M. The rain-max spanning tree problem and some extensions[J]. Infroc Lett, 1978,7(1):10-14.
  • 3YANG Xiaoguang, ZHANG Jianzhong. Some inverse min-max network problems under weighted li and l2 norms with bound constraints on changes[J]. Comb Optim, 2007,13(2) : 123-135.
  • 4LIU L C, YAO E Y. Inverse min-rnax spanning tree problem under the weighted sum-type Hamming distance[M]. Berlin: Springer Publisher, 2007:120-126.
  • 5GUAN Xiucui, ZHANG Jianzhong. Inverse constrained bottleneck problems under weightednorm[J ]. Computers and Operations Research, 2007,34(11) : 3243-3254.
  • 6CHIANG Charles, MAJID Sarrafzadeh, WONG C K. Global Routing Based on Steiner Min-Max Trees[J ]. IEEE Transaction Computer-Aided Design, 1990,9(12) : 1318-1325.
  • 7STOER M, WAGNER F. A simple min cut algorithm[J]. Algorithms Spinger, 1994,44(4):141-147.

引证文献1

沈阳师范大学学报（自然科学版）
2008年 第1期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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