On the Efficiency of the Algorithm for Steiner Minimal Trees

Previous article Next article On the Efficiency of the Algorithm for Steiner Minimal TreesE. J. CockayneE. J. Cockaynehttps://doi.org/10.1137/0118014PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout[1] E. J. Cockayne, On the Steiner problem, Canad. Math. Bull., 10 (1967), 431–450 MR0215750 0161.19203 CrossrefISIGoogle Scholar[2] E. J. Cockayne, Computation of minimal length full Steiner trees on the vertices of a convex polygon, Rep., 14, Dept. of Mathematics, University of Victoria, British Columbia, 1968 Google Scholar[3] E. N. Gilbert and , H. O. Pollak, Steiner minimal trees, SIAM J. Appl. Math., 16 (1968), 1–29 10.1137/0116001 MR0223269 0159.22001 LinkISIGoogle Scholar[4] Z. A. Melzak, On the problem of Steiner, Canad. Math. Bull., 4 (1961), 143–148 MR0125466 0101.13201 CrossrefGoogle Scholar[5] Ivan Niven, Mathematics of Choice, New York, 1965 Google Scholar[6] R. C. Prim, Shortest connecting networks, Bell System Tech. J., 3 (1957), 1398–1401 Google Scholar Previous article Next article FiguresRelatedReferencesCited ByDetails Construction of the Current Steiner Network of the Second Optimality RankJournal of Mathematical Sciences, Vol. 253, No. 4 | 12 February 2021 Cross Ref Bioinformatics Mining and Modeling Methods for the Identification of Disease Mechanisms in Neurodegenerative DisordersInternational Journal of Molecular Sciences, Vol. 16, No. 12 | 7 December 2015 Cross Ref Steiner Minimal Trees: An Introduction, Parallel Computation, and Future WorkHandbook of Combinatorial Optimization | 26 July 2013 Cross Ref Minimum Networks in Uniform Orientation MetricsM. Brazil, D. A. Thomas, and J. F. WengSIAM Journal on Computing, Vol. 30, No. 5 | 27 July 2006AbstractPDF (179 KB)Geometric Optimization Problems for Steiner Minimal Trees in E 3Approximation and Complexity in Numerical Optimization | 1 Jan 2000 Cross Ref Spanning TreesGraph Theory for Programmers | 1 Jan 2000 Cross Ref Steiner Minimal Trees: An Introduction, Parallel Computation, and Future WorkHandbook of Combinatorial Optimization | 1 Jan 1998 Cross Ref Shortest Networks for Smooth CurvesJ. F. WengSIAM Journal on Optimization, Vol. 7, No. 4 | 31 July 2006AbstractPDF (261 KB)A Dynamic Adaptive Relaxation Scheme Applied to the Euclidean Steiner Minimal Tree ProblemFrançois Chapeau-Blondeau, Fabrice Janez, and Jean-Louis FerrierSIAM Journal on Optimization, Vol. 7, No. 4 | 31 July 2006AbstractPDF (270 KB)Linear Steiner Trees for Infinite SpiralsJ. F. WengSIAM Journal on Discrete Mathematics, Vol. 10, No. 3 | 1 August 2006AbstractPDF (270 KB)Full Minimal Steiner Trees on Lattice SetsJournal of Combinatorial Theory, Series A, Vol. 78, No. 1 | 1 Apr 1997 Cross Ref Steiner minimal trees on regular polygons with centreDiscrete Mathematics, Vol. 141, No. 1-3 | 1 Jun 1995 Cross Ref Steiner polygons in the Steiner problemGeometriae Dedicata, Vol. 52, No. 2 | 1 Sep 1994 Cross Ref Variational approach and Steiner minimal trees on four pointsDiscrete Mathematics, Vol. 132, No. 1-3 | 1 Sep 1994 Cross Ref Symmetrization theorem of full steiner treesJournal of Combinatorial Theory, Series A, Vol. 66, No. 2 | 1 May 1994 Cross Ref Determining shortest networks in the Euclidean planeBulletin of the Australian Mathematical Society, Vol. 49, No. 2 | 17 April 2009 Cross Ref A model for determining the cost-effectiveness of T1 transmission in certain integrated networksMathematical and Computer Modelling, Vol. 16, No. 11 | 1 Nov 1992 Cross Ref Degree-five Steiner points cannot reduce network costs for planar setsNetworks, Vol. 22, No. 6 | 1 Oct 1992 Cross Ref Improved computation of plane Steiner Minimal TreesAlgorithmica, Vol. 7, No. 1-6 | 1 Jun 1992 Cross Ref Steiner minimal trees for a class of zigzag linesAlgorithmica, Vol. 7, No. 1-6 | 1 Jun 1992 Cross Ref Two new criteria for finding Steiner hulls in Steiner tree problemsAlgorithmica, Vol. 7, No. 1-6 | 1 Jun 1992 Cross Ref Steiner tree problemsNetworks, Vol. 22, No. 1 | 1 Jan 1992 Cross Ref The role of Steiner hulls in the solution to Steiner tree problemsAnnals of Operations Research, Vol. 33, No. 7 | 1 Jul 1991 Cross Ref A primer of the Euclidean Steiner problemAnnals of Operations Research, Vol. 33, No. 1 | 1 Jan 1991 Cross Ref Using structured steiner trees for hierarchical global routingInternational Journal of Computer Mathematics, Vol. 39, No. 3-4 | 1 Jan 1991 Cross Ref An Improved Algorithm for Steiner TreesDan Trietsch and Frank HwangSIAM Journal on Applied Mathematics, Vol. 50, No. 1 | 10 July 2006AbstractPDF (2423 KB)Interconnecting networks in the plane: The steiner caseNetworks, Vol. 20, No. 1 | 1 Jan 1990 Cross Ref Reduction tests for the steiner problem in grapshNetworks, Vol. 19, No. 5 | 1 Aug 1989 Cross Ref A decomposition theorem on Euclidean Steiner minimal treesDiscrete & Computational Geometry, Vol. 3, No. 4 | 1 December 1988 Cross Ref An Approximation Scheme for Finding Steiner Trees with ObstaclesJ. Scott ProvanSIAM Journal on Computing, Vol. 17, No. 5 | 31 July 2006AbstractPDF (1936 KB)Convexity and the Steiner tree problemNetworks, Vol. 18, No. 1 | 1 Jan 1988 Cross Ref Steiner minimal trees for bar wavesActa Mathematicae Applicatae Sinica, Vol. 3, No. 3 | 1 Jul 1987 Cross Ref Hexagonal coordinate systems and steiner minimal treesDiscrete Mathematics, Vol. 62, No. 1 | 1 Oct 1986 Cross Ref Exact computation of Steiner minimal trees in the planeInformation Processing Letters, Vol. 22, No. 3 | 1 Mar 1986 Cross Ref A linear time algorithm for full steiner treesOperations Research Letters, Vol. 4, No. 5 | 1 Feb 1986 Cross Ref WEAVER: A Knowledge-Based Routing ExpertIEEE Design & Test of Computers, Vol. 3, No. 1 | 1 Feb 1986 Cross Ref Augmenting Euclidean Networks—the Steiner CaseDan TrietschSIAM Journal on Applied Mathematics, Vol. 45, No. 5 | 12 July 2006AbstractPDF (822 KB)An algorithm for the steiner problem in the euclidean planeNetworks, Vol. 15, No. 3 | 1 Jan 1985 Cross Ref The Gilbert and Pollak conjecture—a generalizationNetworks, Vol. 15, No. 3 | 1 Jan 1985 Cross Ref Maximum savings in the Steiner problem in phylogenyJournal of Theoretical Biology, Vol. 107, No. 3 | 1 Apr 1984 Cross Ref An algorithm for the steiner problem in graphsNetworks, Vol. 12, No. 3 | 1 Jan 1982 Cross Ref Steiner's problem and fagnano's result on the sphereMathematical Programming, Vol. 18, No. 1 | 1 Dec 1980 Cross Ref An Improved Program for the Full Steiner Tree ProblemACM Transactions on Mathematical Software, Vol. 3, No. 4 | 1 Dec 1977 Cross Ref Some experiments with Steiner treesNumerische Methoden bei Optimierungsaufgaben Band 3 | 1 Jan 1977 Cross Ref Low cost drainage networksNetworks, Vol. 6, No. 4 | 1 Jan 1976 Cross Ref Improved solutions for some minimal-network test problemsACM SIGMAP Bulletin, No. 16 | 1 Apr 1974 Cross Ref The Generation of Minimal Trees with a Steiner TopologyJournal of the ACM, Vol. 19, No. 4 | 1 Oct 1972 Cross Ref Letter to the EditorInternational Journal of Mathematical Education in Science and Technology, Vol. 3, No. 3 | 1 Jul 1972 Cross Ref Some problems in discrete optimizationMathematical Programming, Vol. 1, No. 1 | 1 Dec 1971 Cross Ref Volume 18, Issue 1| 1970SIAM Journal on Applied Mathematics1-257 History Submitted:12 November 1968Published online:31 July 2006 InformationCopyright © 1970 Society for Industrial and Applied MathematicsPDF Download Article & Publication DataArticle DOI:10.1137/0118014Article page range:pp. 150-159ISSN (print):0036-1399ISSN (online):1095-712XPublisher:Society for Industrial and Applied Mathematics