×

A variational approach to the Steiner network problem. (English) Zbl 0734.05040

Summary: Suppose n points are given in the plane. Their coordinates form a 2n- vector X. To study the question of finding the shortest Steiner network S connecting these points, we allow X to vary over a configuration space. In particular, the Steiner ratio conjecture is well suited to this approach and short proofs of the cases \(n=4,5\) are discussed. The variational approach was used by us to solve other cases of the ratio conjecture \((n=6\), see [the authors, “The Steiner ratio conjecture for six points”, J. Comb. Theory, Ser. A. (to appear)] and for arbitrary n points lying on a circle). Recently, Du and Hwang have given a beautiful complete solution of the ratio conjecture, also using a configuration space approach but with convexity as the major idea. We have also solved Graham’s problem to decide when the Steiner network is the same as the minimal spanning tree, for points on a circle and on any convex polygon, again using the variational method.

MSC:

05C05 Trees
90C35 Programming involving graphs or networks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] D.Z. Du, F.K. Hwang and E.N. Yao, The Steiner ratio conjecture is true for five points, J. Comb. Theory Ser. A 38(1985)230–240. · Zbl 0576.05015 · doi:10.1016/0097-3165(85)90073-1
[2] D.Z. Du, E.N. Yao and F.K. Hwang, A short proof of a result of Pollak on Steiner minimal trees, J. Comb. Theory Ser. A 32(1982)396–400. · Zbl 0507.05028 · doi:10.1016/0097-3165(82)90056-5
[3] M.R. Garey, R.L. Graham and D.S. Johnson, The complexity of computing Steiner minimal trees, SIAM J. Appl. Math. 32(1977)835–859. · Zbl 0399.05023 · doi:10.1137/0132072
[4] E.N. Gilbert and H.O. Pollak, Steiner minimal trees, SIAM J. Appl. Math. 16(1968)1–29. · Zbl 0159.22001 · doi:10.1137/0116001
[5] M. Gromov, Curvature, diameter and Betti numbers, Comment. Math. Helv. 56(1981)179–195. · Zbl 0467.53021 · doi:10.1007/BF02566208
[6] J.B. Kruskal, Jr., On the shortest spanning subtree of a graph and the travelling salesman problem, Proc. Amer. Math. Soc. 7(1956)48–50. · Zbl 0070.18404
[7] W. Meeks and S.T. Yau, Topology of three-dimensional manifolds and the embedding problem in minimal surface theory, Ann. Math. (2) 112(1980)441–485. · Zbl 0458.57007 · doi:10.2307/1971088
[8] Z.A. Melzak, On the problem of Steiner, Can. Math. Bull. 4(1961)143–148. · Zbl 0101.13201 · doi:10.4153/CMB-1961-016-2
[9] H.O. Pollak, Some remarks on the Steiner problem, J. Comb. Theory Ser. A (1978)278–295. · Zbl 0392.05021
[10] R.C. Prim, Shortest connection networks and some generalizations, Bell. Syst. Tech. J. 36(1957)1389–1401.
[11] J.H. Rubinstein and D.A. Thomas, The Steiner ratio conjecture for six points, J. Comb. Theory Ser. A, to appear. · Zbl 0739.05034
[12] J.H. Rubinstein and D.A. Thomas, Critical points for the Steiner ratio conjecture, Preprint. · Zbl 0774.05031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.