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

广义欧几里德Steiner问题的研究与进展 被引量：2

Development of the Generalized Euclidean Steiner Problem
下载PDF
导出
摘要 广义欧几里德Steiner问题是指确定连接平面上一组给定点的满足特定连通性要求的最短网络的问题。本文主要介绍了此问题的研究与进展,在建立了求给定平面点集的最短U-连通(或边连通)生成网络的整数规划模型的基础上,证明了文献[13]中所给的一个例子是错误的,并提出了一些关于广义Steiner问题的进一步研究的问题。 The generalized Euclidean Steiner problem is to find the shortest network satisfying specified connectivity requirements, which connects a set of given points in the Euclidean plane. A survey up to now on this problem is given. A general 0\1 integer linear programming model is presented for finding the shortest U-connected (or edge-connected) spanning network for a set of given points in the plane, by which we show that the counter example in a paper of Hsu and Hu is false. Some problems for further research about Steiner problem are also proposed.
作者 张胜贵 彭书英 李美丽 乔胜宁
机构地区 西北工业大学应用数学系 天津工业大学理学院 西安石油大学数学系
出处 《工程数学学报》 CSCD 北大核心 2005年第4期571-578,共8页 Chinese Journal of Engineering Mathematics
基金 国家自然科学基金(10101021).
关键词 Steiner问题 (广义)欧几里德Steiner问题 k-Steiner比率 Steiner problem (generalized) Euclidean Steiner problem k-Steiner ratio
分类号 O157.5 [理学—基础数学]
  • 相关文献

参考文献21

  • 1Winter P. The Steiner Problem[D]. M. Sc. Thesis, Inst. of Datalogy Univ. of Copenhagen, Denmark (1981).
  • 2Winter P. Steiner problem in networks: a survey[J]. Networks, 1987;17:129-167.
  • 3Hwang F K, Richards D S. Steiner tree problems[J]. Networks, 1992;22:55-89.
  • 4Garey M R, Graham L R, Johnson D S. The complexity of computing Steiner minimal trees[J]. SIAM J Appl Math, 1977;32:835-859.
  • 5Gilbert E N, Pollak H O. Steiner minimal trees[J]. SIAM J Appl Math, 1968;16:1-29.
  • 6张亚明,刘玉峰.Steiner问题的研究及进展[J].东北重型机械学院学报,1996,20(1):51-57. 被引量：2
  • 7Christofides N, Whitlock C A. Network synthesis with connectivity constraints-a survey[A]. In J.P. Brans(Ed.), Operational Research[C], North-Holland, Amsterdam, 1981;81:705-723.
  • 8Grotschel M, Monma C L, Stoer M. Design of survariable networks, Handbook in Operations Research and Management Sciences[M]. (M. Ball, T. Magnanti, C. Monma and G. Nemhauser, Eds), 1993.
  • 9Bondy J A, Murty U S R. Graph theory with applications[M]. New York: North Holland, 1976.
  • 10Monma C L, Shallcross D F. Methods of designing communication networks with certain two-connected survivability constraints[J]. Oper Res, 1989;37:531-541.

共引文献5

同被引文献7

  • 1[1]Monma C L,Shallcross D F.Methods for designing communication networks with certintwo-connected survivabilityconstraints[J].Operations Research,1989,37:531-541.
  • 2[2]Luebke E L,Provan J S.On the structure and complexity of the 2-connectedSteiner network problem in the plane[J].Operations Research Letters,2000,26:111-116.
  • 3[4]Hsu D F,Hu X-D.On shortest two-connected Steiner networks with Euclidean distance[J].Networks,1998,32(2):133-140.
  • 4[5]Li M,Zhang S,Peng S,et al.Shortest 2-connected Steiner network with Euclidean distance[C].Japan Conference on Discrete Computational Geometry,Tokai University,Tokyo,2004.
  • 5[6]Bondy J A,Murty U S R.Graph Theory with Applications[M].New York:Macmillan London and Elsevier,1976.
  • 6[7]Monma C L,Munson B S,Pulleyblank W R.Minimumweight two-connected spanning networks[J].Mathematical Programming,1990,46:153-172.
  • 7[8]Winter P,Zachariasen M.Two-connected Steiner networks:structural properties[J].Operations Research Letters,2005,33:395-402.

引证文献2

工程数学学报
2005年 第4期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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