×

zbMATH — the first resource for mathematics

Minimal networks: a review. (English) Zbl 1359.05117
Sadovnichiy, Victor A. (ed.) et al., Advances in dynamical systems and control. Cham: Springer (ISBN 978-3-319-40672-5/hbk; 978-3-319-40673-2/ebook). Studies in Systems, Decision and Control 69, 43-80 (2016).
Summary: Minimal networks theory is a branch of mathematics that goes back to 17th century and unites ideas and methods of metric, differential, and combinatorial geometry and optimization theory. It is still studied intensively, due to many important applications such as transportation problem, chip design, evolution theory, molecular biology, etc. In this review we point out several significant directions of the theory. We also state some open problems which solution seems to be crucial for the further development of the theory. Minimal networks can be considered as one-dimensional minimal surfaces. The simplest example of such a network is a shortest curve or, more generally, a geodesic. The first ones are global minima of the length functional considered on the curves connecting fixed boundary points. The second ones are the curves such that each sufficiently small part of them is a shortest curve. A natural generalization of the problem appears, if the boundary consists of three and more points, and additional branching points are permitted. Steiner minimal trees are analogues of the shortest curves, and locally minimal networks are generalizations of geodesics. We also include some results concerning so-called minimal fillings and minimal networks in the spaces of compacts.
For the entire collection see [Zbl 1357.00036].

MSC:
05C82 Small world graphs, complex networks (graph-theoretic aspects)
90B10 Deterministic network models in operations research
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Fermat de P., Tannery, H. (eds.): OeuPres, vol. 1, Paris 1891, Supplement: Paris 1922, p. 153 (1643)
[2] Chanderjit B.: Limitations To Algorithm Solvability: Galois Methods and Models of Computation, Computer Science Technical Reports, Paper 486 (1986)
[3] Harary, F.: Graph Theory. Addison-Wesley, MA (1969) · Zbl 0182.57702
[4] Ivanov, A.O., Tuzhilin, A.A.: Minimal Spanning Trees on Infinite Sets. Fund. i Prikl. Matem. 20(2), 89-103 (2015). (in Russian, English translation to appear in J. of Math. Sci., 2016)
[5] Ivanov, A.O., Nikonov, I.M., Tuzhilin, A.A.: Sets admitting connection by graphs of finite length. Matem. Sbornik 196(6), 71-110 (2005). (Sbornik: Math., 196 (6), pp. 845-884) · Zbl 1081.54024 · doi:10.4213/sm1365
[6] Burago D., Burago Yu., and Ivanov S.: A Course in Metric Geometry, Graduate Studies in Math., 33, A.M.S., Providence, RI (2001) · Zbl 0981.51016
[7] Gergonne, J.D.: Solutions purement gèomètriques des problèmes de minimis proposès aux pages 196, 232 et 292 de ce volume, et de divers autres problèmes analogues. Annales de Mathèmatiques pures et appliquèes 1, 375-384 (1810)
[8] Melzak, Z.A.: On the problem of Steiner. Canad. Math. Bull. 4, 143-148 (1960) · Zbl 0101.13201 · doi:10.4153/CMB-1961-016-2
[9] Bopp, K.: Über das kürzeste Verbindungssystem zwischen vier Punkten. Universität Göttingen, PhDthesis (1879)
[10] Jarnik, V., Kössler, M.: O minimalnich grafeth obeahujiicich n danijch bodu. Cas. Pest. Mat. a. Fys. 63, 223-235 (1934)
[11] Brazil, M., Graham, R.L., Thomas, D.A., Zachariasen, M.: On the history of the euclidean Steiner tree problem. Arch. Hist. Exact Sci. pp. 1-30 (2013) · Zbl 1295.05002
[12] Courant, R., Robbins, G.: What Is Mathematics?. Oxford University Press, London (1941) · Zbl 0060.12302
[13] Ivanov, A.O., Tuzhilin, A.A.: Extreme Networks Theory. In-t Komp. Issl, Moscow, Izhevsk (2003). [in Russian]
[14] Ivanov, A.O., Tuzhilin, A.A.: Geometry of minimal networks and the one-dimensional plateau problem. Uspekhi Matem. Nauk 47(2), 53-115 (1992). (Russian Math. Surv., 47 (2), pp. 59-131 (1992)) · Zbl 0792.90083
[15] Ivanov, A.O., Tuzhilin, A.A.: Branching geodesics in normed spaces. Izv. RAN, Ser. Matem. 66(5), 33-82 (2002). (Izvestiya: Math., 66 (5) pp. 905-948 (2002)) · Zbl 1112.90377 · doi:10.4213/im402
[16] Ivanov, A.O., Van Hong, L., Tuzhilin, A.A.: Nontrivial critical networks. Singularities of lagrangians and a criterion for criticality. Matem. Zametki 69(4), 566-580 (2001). (Math. Notes, 69 (4), pp. 514-526 (2001)) · Zbl 0986.05031 · doi:10.4213/mzm523
[17] Swanepoel, K.: The local steiner problem in normed planes. Networks 36(2), 104-113 (2000) · Zbl 0971.90075 · doi:10.1002/1097-0037(200009)36:2<104::AID-NET5>3.0.CO;2-K
[18] Il’yutko, D.P.: Locally minimal trees in · Zbl 1134.49028 · doi:10.4213/mzm298
[19] Il’yutko, D.P.: Branching extremals of the functional of · doi:10.4213/sm1559
[20] Il’yutko, D.P.: Geometry of extreme networks in
[21] Sankoff, D.: Minimal mutation trees of sequences. SIAM J. Appl. Math. 28, 35-42 (1975) · Zbl 0315.05101 · doi:10.1137/0128004
[22] Ivanov, A.O., Tuzhilin, A.A.: One-dimensional Gromov minimal filling problem. Matem. Sbornik 203(5), 65-118 (2012). (Sbornik: Math., 203 (5), pp. 677-726 (2012)) · Zbl 1248.05057
[23] Gromov, M.: Filling Riemannian manifolds. J. Diff. Geom. 18(1), 1-147 (1983) · Zbl 0515.53037
[24] Cormen, Th.H., Leiserson, Ch.E., Rivest, R.L., Stein, C.: Introduction To Algorithms, 3rd edn. MIT Press, Cambridge (2009) · Zbl 1187.68679
[25] Gilbert, E.N., Pollak, H.O.: Steiner minimal trees. SIAM J. Appl. Math. 16(1), 1-29 (1968) · Zbl 0159.22001 · doi:10.1137/0116001
[26] Ivanov, A.O., S’edina, O.A., Tuzhilin, A.A.: The structure of minimal Steiner trees in the neighborhoods of the lunes of their edges. Matem. Zametki 91(3), 352-370 (2012). (Math. Notes, 91 (3), pp. 339-353 (2012)) · Zbl 1282.05030 · doi:10.4213/mzm8533
[27] Ivanov, A.O., Tuzhilin, A.A.: The twist number of planar linear trees. Matem. Sbornik 187(8), 41-92 (1996). (Sbornik: Math., 187 (8), pp. 1149-1195) · Zbl 0868.05020 · doi:10.4213/sm151
[28] Ivanov, A.O.: The geometry of plane locally minimal binary trees. Matem. Sbornik 186(9), 45-76 (1995). (Sbornik: Math., 186 (9), pp. 1271-1301 (1995))
[29] Ivanov, A.O., Tuzhilin, A.A.: Minimal Surfaces. In: Fomenko, A. (ed.) The Steiner Problem for Convex Boundaries, General Case. Advances in Soviet Mathematics, pp. 15-92. American Mathematical Society, Providence (1993)
[30] Ivanov, A.O., Tuzhilin, A.A.: Minimal Networks. Steiner Problem and Its Generalizations. CRC Press, Boca Raton (1994) · Zbl 0859.90115
[31] Ivanov, A.O., Tuzhilin, A.A.: Branching Geodesics. Geometry of Locally Minimal Networks. Russian Math. and Sci. Researches, vol. 5. Edwin-Mellen Press, Lewiston (1999). [in Russian] · Zbl 1112.90377
[32] Ivanov, A.O., Tuzhilin, A.A.: The Steiner problem in the plane or in plane minimal nets. Matem. Sbornik 182(12), 1813-1844 (1991). (Math. of the USSR-Sbornik, 74 (2), pp. 555-582 (1993)) · Zbl 0751.05029
[33] Eremin, AYu.: A formula for the weight of a minimal filling of a finite metric space. Matem. Sbornik 204(9), 51-72 (2013). (Sbornik: Math., 204 (9), pp. 1285-1306 (2013)) · Zbl 1282.05075 · doi:10.4213/sm7835
[34] Zaretskij, K.A.: Construction of a tree from the collection of distances between suspending vertices. Uspekhi Matem. Nauk 20(6), 90-92 (1965). [in Russian] · Zbl 0151.33302
[35] Simões-Pereira, J.M.S.: A note on the tree realizability of a distance matrix. J. Comb. Theory 6, 303-310 (1969) · Zbl 0177.26903 · doi:10.1016/S0021-9800(69)80092-X
[36] Smolenskij, E.A.: About a linear denotation of graphs. Zh. Vychisl. Mat. Mat. Fiz. 2(2), 371-372 (1962)
[37] Hakimi, S.L., Yau, S.S.: Distance matrix of a graph and its realizability. Quart. Appl. Math. 12, 305-317 (1975) · Zbl 0125.11804
[38] Rubleva, O.V.: The additivity criterion for finite metric spaces and minimal fillings, Vestnik MGU. Matem. Mech. 1(2), 8-11 (2012). (Moscow Univ. Math. Bull., 67 (2), pp. 52-54 (2012)) · Zbl 1307.05099
[39] Ovsyannikov, Z.N.: Pseudo-additive Metric Spaces and Minimal Fillings, Diploma Thesis. Mech. Math, MGU (2013)
[40] Du, D.Z., Hwang, F.K., Weng, J.F.: Steiner minimal trees for regular polygons. Discrete Comput. geom. 2, 65-84 (1987) · Zbl 0607.05022 · doi:10.1007/BF02187871
[41] Du, D.Z., Hwang, F.K., Weng, J.F.: Steiner minimal trees on zig-zag lines. Trans. Am. Math. Soc. 278(1), 149-156 (1983) · Zbl 0523.51018 · doi:10.1090/S0002-9947-1983-0697066-5
[42] Chung, F.R.K., Graham, R.L.: Steiner trees for ladders. Ann. Discr. Math. (2), 173-200 (1978) · Zbl 0384.05030
[43] Du, D.Z., Hwang, F.K., Chao, S.C.: Steiner minimal tree for points on a circle. Proc. Am. Math. Soc. 95(4), 613-618 (1985) · Zbl 0596.05022 · doi:10.1090/S0002-9939-1985-0810173-6
[44] Rubinstein, J.H., Thomas, D.A.: Graham’s problem on shortest networks for points on a circle. Algorithmica 7, 193-218 (1992) · Zbl 0748.05051 · doi:10.1007/BF01758758
[45] Du, D.Z., Hwang, F.K.: Steiner minimal trees on chinese checkerboards. Math. Mag. 64(5), 332-339 (1991) · Zbl 0766.05020 · doi:10.2307/2690650
[46] Chung, F.R.K., Gardner, M., Graham, R.L.: Steiner trees on a checkboard. Math. Mag. 62(2), 83-96 (1989) · Zbl 0681.05018 · doi:10.2307/2690388
[47] Ivanov, A.O., Tuzhilin, A.A.: Uniqueness of Steiner minimal trees on boundaries in general position. Matem. Sbornik 197(9), 55-90 (2006). (Sbornik: Math., 197 (9), pp. 1309-1340 (2006)) · Zbl 1168.05304 · doi:10.4213/sm1463
[48] Ivanov, A.O., Tuzhilin, A.A.: Stabilization of locally minimal trees. Matem. Zametki 86(4), 512-524 (2009). (Math. Notes, 86 (4), pp. 483-492 (2009)) · Zbl 1220.05018 · doi:10.4213/mzm4023
[49] Ivanov, A.O., Tuzhilin, A.A.: Minimal Surfaces. In: Fomenko, A. (ed.) The Steiner Problem for Convex Boundaries, the Regular Case. Advances in Soviet Mathematics, vol. 15, pp. 93-131
[50] Tuzhilin, A.A.: Minimal binary trees with regular boundary: the case of skeletons with four ends. Matem. Sbornik 187(4), 117-159 (1996). (Sbornik: Math., 187 (4), pp. 581-622, (1996)) · Zbl 0868.05021 · doi:10.4213/sm124
[51] Tuzhilin, A.A.: Minimal binary trees with a regular boundary: the case of skeletons with five endpoints. Matem. Zametki 61(6), 906-921 (1997). (Math. Notes, 61 (6), pp. 758-769 (1997)) · Zbl 0941.05018 · doi:10.4213/mzm1574
[52] Tuzhilin, A.A.: Complete classification of locally minimal binary trees with a regular boundary whose dual triangulations are skeletons. Fundam. Prikl. Mat. 2(2), 511-562 (1996). [in Russian] · Zbl 0901.05035
[53] Ivanov A.O., Tuzhilin A.A.: Planar Local Minimal Binary Trees with Convex, Quasiregular, and Regular Boundaries, Sonderforschungsbereich 256 Preprint (1997)
[54] Fomenko, A.T.: Topological Variational Problems. Izd-vo MGU, Moscow,1984. Gordon and Breach Science Publishers, New York (1990) · Zbl 0716.53004 · doi:10.1007/978-94-009-1856-6
[55] Heppes, A.: Isogonal Spherische Netze. Ann. Univ. Sci., Budapest, Sect. Math. 7, 4-48 (1964)
[56] Ivanov, A.O., Ptitsyna, I.V., Tuzhilin, A.A.: Classification of closed minimal networks on flat two-dimensional tori. Matem. Sbornik 183(12), 3-44 (1992). (Sbornik. Math., 77 (2), pp. 391-425 (1994)) · Zbl 0818.90125
[57] Ptitsyna, I.V.: Classification of closed minimal networks on flat klein bottles, Vestnik MGU. Ser. Matem. Mech. (2), 15-22 (1995). (Moscow Univ. Math. Bull., 50 (2), pp. 13-19 (1995)) · Zbl 0886.57017
[58] Ptitsyna, I.V.: Classification of closed minimal networks on tetrahedra. Matem. Sbornik 185(5), 119-138 (1994). (Sbornik. Math., 82 (1), pp. 101-116 (1995)) · Zbl 0841.05046
[59] Strelkova, N.P.: Realization of plane graphs as closed locally minimal nets on convex polyhedra. Dokl. RAN 435(1), 1-3 (2010). (Doklady Math., 82 (3), pp. 939-941 (2010)) · Zbl 1217.52003
[60] Strelkova, N.P.: Closed locally minimal networks on surfaces of convex polyhedra. Model. Anal. Inf. Sist. 20(5), 117-147 (2013). [in Russian]
[61] Alexandrov, A.D.: Convex Polyhedra. Gos. Izd-vo Tekh.-Teor. Liter., Moscow-Leningrad, 1950. Springer, Berlin (2005) · Zbl 1133.52301
[62] Strelkova, N.P.: Closed locally minimal nets on tetrahedra. Matem. Sbornik 202(1), 141-160 (2011). (Sbornik: Math., 202 (1), pp. 135-153 (2011)) · Zbl 1223.05134 · doi:10.4213/sm7662
[63] Maxwell J.C.: Cambridge Philos. Mag. (1864)
[64] Maxwell J.C.: Trans. Roy. Soc. vol. 26, Edinburgh (1869)
[65] Ivanov, A.O., Tuzhilin, A.A.: Generalized Maxwell formula for the length of a minimal tree with a given topology, Vestnik MGU. Ser. Matem. Mech. 1(3), 7-14 (2010). (Moscow Univ. Math. Bull., 65 (3), pp. 100-106 (2010)) · Zbl 1304.05017
[66] Bannikova, A.G., Ilyutko, D.P., Nikonov, I.M.: The length of an extremal network in a normed space: Maxwell formula. Sovrem. Matem. Fundam. Napravl. 51, 5-20 (2016). (J. of Math. Sci., 214 (5), pp. 593-608 (2016)) · Zbl 1337.05092
[67] Ivanov, A.O., Ovsyannikov, Z.N., Strelkova, N.P., Tuzhilin, A.A.: One-dimensional minimal fillings with negative edge weights. Vestnik MGU, Ser. Matem. Mech. 1(5), 3-8 (2012). (Moscow Univ. Math. Bull., 67 (5), pp. 189-194 (2012)) · Zbl 1322.05047
[68] Pakhomova, A.S.: The estimates for Steiner subratio and Steiner-Gromov ratio. Vestnik MGU, Ser. Mat. Mech. (1), 17-25 (2014). (Moscow Univ. Math. Bull., 69 (1), pp. 16-23 (2014)) · Zbl 1333.51004
[69] Hwang, F.K.: On Steiner minimal trees with rectilinear distance. SIAM J. Appl. Math. 30, 104-114 (1976) · Zbl 0322.05101 · doi:10.1137/0130013
[70] Innami, N., Kim, B.H.: Steiner ratio for hyperbolic surfaces. Proc. Jpn. Acad. 82, 77-79 (2006) · Zbl 1114.53034 · doi:10.3792/pjaa.82.77
[71] Ivanov, A.O., Tuzhilin, A.A.: Steiner ratio. the state of the art. Math. Quest. Cybern. 11, 27-48 (2002) · Zbl 1228.05121
[72] Du, D.-Z., Hwang, F.K.: A proof of the Gilbert-Pollak conjecture on the Steiner ratio. Algorithmica 7, 121-135 (1992) · Zbl 0774.05027 · doi:10.1007/BF01758755
[73] Innami, N., Kim, B.H., Mashiko, Y., Shiohama, K.: The Steiner ratio Gilbert-Pollak conjecture may still be open. Algorithmica 57(4), 869-872 (2010) · Zbl 1220.05120 · doi:10.1007/s00453-008-9254-3
[74] Ivanov, A.O., Tuzhilin, A.A.: The Steiner ratio Gilbert-Pollak conjecture is still open. Clarification statement. Algorithmica 62(1-2), 630-632 (2012) · Zbl 1239.05033 · doi:10.1007/s00453-011-9508-3
[75] Ivanov, A.O., Tuzhilin, A.A.: Branched coverings and steiner ratio. Int. Trans. Op. Res. 2, 1-8 (2015) · Zbl 1348.90597
[76] Ivanov, A.O., Tuzhilin, A.A., Cieslik, D.: Steiner Ratio for Manifolds. Matem. Zametki 74(3), 387-395 (2003). (Math. Notes, 74 (3), pp. 367-374 (2003)) · Zbl 1066.52009 · doi:10.4213/mzm272
[77] Cieslik, D.: The Steiner Ratio of Metric Spaces (Report. · Zbl 1017.05035
[78] Ivanov, A.O., Tuzhilin, A.A.: Discrete Geometry and Algebraic Combinatorics. In: Barg, A., Musin, O. (eds.) Minimal Fillings of Finite Metric Spaces: The State of the Art. Contemporary Mathematics, vol. 625, pp. 9-35. AMS, Providence (2014) · Zbl 1331.05071
[79] Ivanov A.O., Nikolaeva N.K., Tuzhilin A.A.: The Gromov-Hausdorff Metric on the Space of Compact Metric Spaces is Strictly Intrinsic, arXiv e-prints, · Zbl 1377.54030
[80] Ivanov A.O., Iliadis S., Tuzhilin A.A.: Realizations of Gromov-Hausdorff Distance, arXiv e-prints,
[81] Chowdhury S., Memoli F.: Constructing Geodesics on the Space of Compact Metric Spaces, arXiv e-prints,
[82] ; pp.
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.