Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Euclidean Steiner trees optimal with respect to swapping 4-point subtrees

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

The Steiner tree problem in Euclidean space \(E^3\) asks for a minimum length network \(T\), called a Euclidean Steiner Minimum Tree (ESMT), spanning a given set of points. This problem is NP-hard and the hardness is inherently due to the number of feasible topologies (underlying graph structure of \(T\)) which increases exponentially as the number of given points increases. Planarity is a very strong condition that gives a big difference between the ESMT problem in the Euclidean plane \(E^2\) and in Euclidean \(d\)-space \(E^d (d\ge 3)\): the ESMT problem in the plane is practically solvable whereas the ESMT problem in \(d\)-space is really intractable. The simplest tree rearrangement technique is to repeatedly replace a subtree spanning four nodes in \(T\) with another subtree spanning the same four nodes. This technique is referred to as the Swapping 4-point Topology/ Tree technique in this paper. An indicator (or quasi-indicator) of \(T\) plays a similar role in the optimization of the length \(L(T)\) of \(T\) in the discrete topology space (the underlying graph structure of \(T\)) to the derivative of a differentiable function which indicates a fastest direction of descent. \(T\) will be called S4pT-optimal if it is optimal with respect to swapping 4-point subtrees. In this paper we first make a complete analysis of 4-point trees in Euclidean space exploring all possible types of 4-point trees and their properties. We review some known indicators of 4-point ESMTs in \(E^2\), and give some simple geometric proofs of these indicators. Then, we translate these indicators to \(E^3\), producing eight quasi-indicators in \(E^3\) using computational experiments, the best quasi-indicator \(\rho _\mathrm{osr}\) is sifted with an effectiveness for randomly generated 4-point sets as high as 98.62 %. Finally we show how \(\rho _\mathrm{osr}\) is used to find an S4pT-optimal ESMT on 14 probability vectors in \(4d\)-space with a detailed example.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11

Similar content being viewed by others

References

  1. Badri, T.N.: Steiner minimal trees in three-dimensional Euclidean space. PhD Dissertation, University of Massachusetts, USA http://scholarworks.umass.edu/dissertations/AAI3039336 (2002)

  2. Brazil, M., Grossmann, P.A., Lee, D.H., Rubinstein, J.H., Thomas, D.A., Wormald, N.C.: Decline design in underground mines using constrained path optimisation. Min. Technol. Trans. Inst. Min. Metall. Sect. A 117, 93–99 (2008)

    Google Scholar 

  3. Brazil, M., Thomas, D.A., Nielsen, B.K., Winter, P., Wulff-Nilsen, C., Zachariasen, M.: A novel approach to phylogenetic trees: d-dimensional geometric Steiner trees. Networks 53(2), 104–111 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  4. Du, D.-Z., Hu, X.: Steiner Tree Problems in Computer Communication Networks. World Scientific, Singapore (2008)

    Book  MATH  Google Scholar 

  5. Du, X., Du, D.-Z., Gao, B., Que, L.: A simple proof for a result of Ollenrenshaw on Steiner trees. In: Du, D.-Z., Sun, J. (eds.) Advances in Optimization and Approximation, pp. 68–71 (1994)

  6. Ewens, W.J., Grant, G.R.: Statistical Methods in Bioinformatics: An Introduction. Springer, USA (2005)

    Book  Google Scholar 

  7. Fampa, M., Anstreicher, K.M.: An improved algorithm for computing Steiner minimal trees in Euclidean \(d\)-pace. Discret. Optim. 5(2), 530–540 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  8. Felsenstein, J.: Inferring Phylogenies. Sinauer Associates Inc, Sunderland (2004)

    Google Scholar 

  9. Garey, M.R., Graham, R.L., Johnson, D.S.: The complexity of computing Steiner minimal trees. SIAM J. Appl. Math. 32, 835–859 (1977)

    Article  MATH  MathSciNet  Google Scholar 

  10. Gilbert, E.N., Pollak, H.O.: Steiner minimal trees. SIAM J. Appl. Math. 16, 1–29 (1968)

    Article  MATH  MathSciNet  Google Scholar 

  11. Grant, M., Boyd, S.: CVX: Matlab software for disciplined convex programming, version 1.21 (2011)

  12. Hwang, F.K., Richards, D.S., Winter, P.: The Steiner Tree Problem, Annals of Discrete Mathematics, 53rd edn. Elsevier Science Publishers, Amsterdam (1992)

    Google Scholar 

  13. Karp, R.M.: Ruducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)

    Chapter  Google Scholar 

  14. Melzak, Z.A.: On the problem of Steiner. Can. Math. Bull. 4, 143–148 (1961)

    Article  MATH  MathSciNet  Google Scholar 

  15. Mondaini, R. P.: Euclidean full Steiner trees and the modelling of biomolecular structures In: Proceedings of the Biomat, pp. 247–258 (2006)

  16. Ollerenshaw, K.: Minimum networks linking four points in a plane. Inst. Math. Appl. 15, 208–211 (1978)

    MathSciNet  Google Scholar 

  17. Pollak, H.O.: Some remarks on the Steiner problem. J. Comb. Theor. Ser. A 24, 278–295 (1978)

    Article  MATH  MathSciNet  Google Scholar 

  18. Rubinstein, J.H., Thomas, D.A.: A variational approach to the Steiner network problem. Ann. Oper. Res. 33, 481–499 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  19. Rubinstein, J.H., Thomas, D.A., Weng, J.F.: Minimum networks for four points in space. Geometriae Dedicata 93, 57–70 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  20. Smith, W.D.: How to find Steiner minimal trees in Euclidean \(d\)-space. Algorithmica 7, 137–177 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  21. Smith, J.M., Jang, Y., Kim, M.K.: Steiner minimal trees, twist angles, and the protein folding problem, proteins: structure. Funct. Bioinform. 66, 889–902 (2007)

    Article  Google Scholar 

  22. Takahashi, K., Nei, M.: Efficiencies of fast algorithms of phylogenetic inference under the criteria of maximum parsimony, minimum evolution, and maximum likelihood when a large number of sequences are used. Mol. Biol. Evol. 17, 1251–1258 (2000)

    Article  Google Scholar 

  23. Tria, F., Caglioti, E., Loreto, V., Pagnanil, A.: A stochastic local search algorithm for distance-based phylogeny reconstruction. Mol. Biol. Evol. 27, 2587–2595 (2010)

    Article  Google Scholar 

  24. Weng, J.F.: Generalized Steiner problem and hexagonal coordinate system (in Chinese). Acta Math. Appl. Sinica 8, 383–397 (1985)

    MATH  MathSciNet  Google Scholar 

  25. Weng, J.F.: Variational approach and Steiner minimal trees on four points. Discret. Math. 132, 349–362 (1994)

    Article  MATH  Google Scholar 

  26. Weng, J.F.: Steiner trees, coordinate systems and NP-hardness. In: Du, D.-Z., Smith, J.M., Rubinstein, J.H. (eds.) Advances in Steiner Trees, pp. 63–80. KluwerAcademic Publishers, London (2000)

    Chapter  Google Scholar 

  27. Weng, J.F.: Identifying Steiner minimal trees on four points in space. Discret. Math. Algorithms Appl. 1, 401–411 (2009)

    Article  MATH  Google Scholar 

  28. Weng, J.F., Smith, J.M., Brazil, M., Thomas, D.A.: Equivalence, indicators, quasi-indicators and optimal Steiner topologies on four points in space. Fundamenta Informaticae 84, 135–149 (2008)

    MATH  MathSciNet  Google Scholar 

  29. Weng, J.F., Thomas, A., Mareels, I.: Maximum parsimony, substitution model and probability phylogenetic trees. J. Comput. Biol. 18, 67–80 (2011)

    Article  MathSciNet  Google Scholar 

  30. Weng, J.F., Mareels, I., Thomas, D.A.: Probability Steiner trees and maximum parsimony in phylogenetic analysis. J. Math. Biol. 64(7), 1225–1251 (2012)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mechanical Engineering, The University of Melbourne, Melbourne, VIC, 3010, Australia

    Doreen A. Thomas & Jia F. Weng

Authors
  1. Doreen A. Thomas
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jia F. Weng
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Doreen A. Thomas.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Thomas, D.A., Weng, J.F. Euclidean Steiner trees optimal with respect to swapping 4-point subtrees. Optim Lett 8, 1337–1359 (2014). https://doi.org/10.1007/s11590-013-0660-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-013-0660-3

Keywords

Search

Navigation