×

Euclidean Steiner trees optimal with respect to swapping 4-point subtrees. (English) Zbl 1292.90306

Summary: The Steiner tree problem in the 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 the Euclidean \(d\)-space \(E^d\) \((d\geq 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.

MSC:

90C35 Programming involving graphs or networks

Software:

CVX
PDFBibTeX XMLCite
Full Text: DOI Link

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)
[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) · Zbl 1168.92035 · doi:10.1002/net.20279
[4] Du, D.-Z., Hu, X.: Steiner Tree Problems in Computer Communication Networks. World Scientific, Singapore (2008) · Zbl 1156.90014
[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) · Zbl 0829.90129
[6] Ewens, W.J., Grant, G.R.: Statistical Methods in Bioinformatics: An Introduction. Springer, USA (2005) · Zbl 1138.92001
[7] Fampa, M., Anstreicher, K.M.: An improved algorithm for computing Steiner minimal trees in Euclidean $$d$$ d -pace. Discret. Optim. 5(2), 530–540 (2008) · Zbl 1152.90663 · doi:10.1016/j.disopt.2007.08.006
[8] Felsenstein, J.: Inferring Phylogenies. Sinauer Associates Inc, Sunderland (2004)
[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) · Zbl 0399.05023 · doi:10.1137/0132072
[10] Gilbert, E.N., Pollak, H.O.: Steiner minimal trees. SIAM J. Appl. Math. 16, 1–29 (1968) · Zbl 0159.22001 · doi:10.1137/0116001
[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) · Zbl 0774.05001
[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)
[14] Melzak, Z.A.: On the problem of Steiner. Can. Math. Bull. 4, 143–148 (1961) · Zbl 0101.13201 · doi:10.4153/CMB-1961-016-2
[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)
[17] Pollak, H.O.: Some remarks on the Steiner problem. J. Comb. Theor. Ser. A 24, 278–295 (1978) · Zbl 0392.05021 · doi:10.1016/0097-3165(78)90058-4
[18] Rubinstein, J.H., Thomas, D.A.: A variational approach to the Steiner network problem. Ann. Oper. Res. 33, 481–499 (1991) · Zbl 0734.05040 · doi:10.1007/BF02071984
[19] Rubinstein, J.H., Thomas, D.A., Weng, J.F.: Minimum networks for four points in space. Geometriae Dedicata 93, 57–70 (2002) · Zbl 1009.05042 · doi:10.1023/A:1020389712969
[20] Smith, W.D.: How to find Steiner minimal trees in Euclidean $$d$$ d -space. Algorithmica 7, 137–177 (1992) · Zbl 0751.05028 · doi:10.1007/BF01758756
[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) · doi:10.1002/prot.21257
[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) · doi:10.1093/oxfordjournals.molbev.a026408
[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) · doi:10.1093/molbev/msq154
[24] Weng, J.F.: Generalized Steiner problem and hexagonal coordinate system (in Chinese). Acta Math. Appl. Sinica 8, 383–397 (1985) · Zbl 0574.05047
[25] Weng, J.F.: Variational approach and Steiner minimal trees on four points. Discret. Math. 132, 349–362 (1994) · Zbl 0808.05037 · doi:10.1016/0012-365X(94)90244-5
[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) · Zbl 0981.68120
[27] Weng, J.F.: Identifying Steiner minimal trees on four points in space. Discret. Math. Algorithms Appl. 1, 401–411 (2009) · Zbl 1221.05063 · doi:10.1142/S1793830909000324
[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) · Zbl 1154.90018
[29] Weng, J.F., Thomas, A., Mareels, I.: Maximum parsimony, substitution model and probability phylogenetic trees. J. Comput. Biol. 18, 67–80 (2011) · doi:10.1089/cmb.2009.0232
[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) · Zbl 1279.92061 · doi:10.1007/s00285-011-0442-4
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.