×

Graham’s problem on shortest networks for points on a circle. (English) Zbl 0748.05051

Given a finite set of points \(x_ 1,x_ 2,\dots,x_ n\) in the Euclidean plane. The problem of finding a network of smallest total length which connects up the points is called the Steiner problem and a solution is a Steiner tree or a Steiner minimum tree. When the points are located on a circle of radius \(r\) with \(x_ i\) adjacent to \(x_{i+1}\), \(1\leq i\leq n-1\) and at most one edge \(x_ ix_{i+1}\) and \(x_ nx_ 1\) has length greater than \(r\), the authors prove that a Steiner tree consists of all edges \(x_ ix_{i+1}\) plus \(x_ nx_ 1\), \(1\leq i\leq n-1\) with the longest edge removed.

MSC:

05C12 Distance in graphs
05C05 Trees
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] D. Z. Du, F. K. Hwang, and S. C. Chao, Steiner Minimal Tree for Points on a Circle,Proc. Amer. Math. Soc.,95 (1985), 613–618. · Zbl 0596.05022
[2] 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
[3] E. N. Gilbert and H. O. Pollak, Steiner Minimal Trees,SIAM J. Appl. Math.,16 (1968), 1–29. · Zbl 0159.22001
[4] R. L. Graham, Some Results on Steiner Minimal Trees, Unpublished manuscript dated 11 May 1967.
[5] Z. A. Melzak, On the Problem of Steiner,Canad. Math. Bull,4 (1961), 143–148. · Zbl 0101.13201
[6] H. O. Pollak, Some Remarks on the Steiner Problem,J. Combin. Theory Ser. A,24 (1978), 278–295. · Zbl 0392.05021
[7] J. H. Rubinstein and D. A. Thomas, A Variational Approach to the Steiner Network Problem, Preprint. · Zbl 0734.05040
[8] J. H. Rubinstein and D. A. Thomas, Critical Points for the Steiner Ratio Conjecture, Preprint. · Zbl 0774.05031
[9] J. H. Rubinstein and D. A. Thomas, The Steiner Ratio Conjecture for Cocircular Points, Preprint. · Zbl 0774.05031
[10] J. H. Rubinstein and D. A. Thomas, The Steiner Ratio Conjecture for Six Points, Preprint. · Zbl 0739.05034
[11] J. H. Rubinstein, D. A. Thomas, and J. F. Weng, Degree Five Steiner Points Cannot Reduce Network Costs for Planar Sets, Preprint. · Zbl 0774.05032
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.