Minimal binary trees with regular boundary: the case of sceletons with four ends

A. A. Tuzhilin

Sbornik. Mathematics, Tome 187 (1996) no. 4, pp. 581-622

Résumé

This work continues an investigation of locally minimal binary trees spanning the vertices of regular polygons. The technique developed has led to essential progress in the solution of this problem.

Bibliographie

[1] Clark R. C., “Communication networks, soap films and vectors”, Phys. Ed., 16 (1981), 32–37 | DOI

[2] Cockayne E. J., “On the Steiner problem”, Canad. J. Math., 10 (1967), 431–450 | MR | Zbl

[3] Dijkstra E. W., “A note on two problems with connection with graphs”, Numer. Math., 1:5 (1959), 269–271 | DOI | MR | Zbl

[4] Du D. Z., Hwang F. K., “A New Bound for the Steiner Ratio”, Trans. Amer. Math. Soc., 278:1 (1983), 137–148 | DOI | MR | Zbl

[5] Du D. Z., Hwang F. K., A Proof of Gilbert–Pollak's Conjecture on the Steiner Ratio, DIMACS Technical Report No 90–72, 1990

[6] Du D. Z., Hwang F. K., “An approach for proving lower bounds: solution of Gilbert–Pollak's Conjecture on the Steiner Ratio”, Proc. of the 31 st annual symp. on found. of comp. science, 1990

[7] Du D. Z., Hwang F. K., Chao S. C., “Steiner minimal trees for points on a circle”, Proc. Amer. Math. Soc., 95:4 (1985), 613–618 | DOI | MR | Zbl

[8] Du D. Z., Hwang F. K., Weng J. F., “Steiner minimal trees for points on a zig-zag lines”, Trans. Amer. Math. Soc., 278:1 (1983), 149–156 | DOI | MR | Zbl

[9] Du D. Z., Hwang F. K., Weng J. F., “Steiner minimal trees for Regular Polygons”, Disc. and Comp. Geometry, 2 (1987), 65–84 | DOI | MR | Zbl

[10] Du D. Z., Hwang F. K., Yao E. N., “The Steiner ratio conjecture is true for five points”, J. Combin Th. Ser. A38, 1985, 230–240 | MR | Zbl

[11] Du D. Z., Hwang F. K., Song G. D., Ting G. T., “Steiner minimal trees on sets of four points”, Discr. and Comp. Geometry, 2 (1987), 401–414 | DOI | MR | Zbl

[12] Garey M. R., Graham R. L., Johnson D. S., “Some $NP$-complete geometric problems”, Eighth Annual Symp. on Theory of Comput., 1976, 10–22 | MR | Zbl

[13] Gilbert E. N., Pollak H. O., “Steiner minimal trees”, SIAM J. Appl. Math., 16:1 (1968), 1–29 | DOI | MR | Zbl

[14] Hildebrandt S., Tromba A., Mathematics and optimal form, Scientific American Books, Inc., New York, 1984 | MR

[15] Hwang F. K., “A linear time algorithm for full Steiner trees”, Oper. Res. Letter, 5 (1986), 235–237 | DOI | MR

[16] Hwang F. K., Weng J. F., “Hexagonal coordinate Systems and Steiner minimal trees”, Disc. Math., 62 (1986), 49–57 | DOI | MR | Zbl

[17] Hwang F. K., Richards D., Winter P., “The Steiners Tree Problem” (to appear) , Elsevier Science Publishers | MR

[18] Jarnik V., Kössler M., “O minimalnich grafeth obeahujicich n danijch bodu”, Cas. Pest. Mat. a Fys., 63 (1934), 223–235 | Zbl

[19] Kruskal J. B., “On the shortest spanning subtree of a graph and traveling salesman problem”, Proc. Amer. Math. Soc., 7 (1956), 48–50 | DOI | MR | Zbl

[20] Melzak Z. A., “On the problem of Steiner”, Canad. Math. Bull., 4 (1960), 143–148 | MR

[21] Melzak Z. A., Companion to concrete mathematics, Wiley-Interscience, New York, 1973 | MR | Zbl

[22] Pollak H. O., “Some remarks on the Steiner problem”, J. Combin. Thy. Ser. A24, 1978, 278–295 | DOI | MR | Zbl

[23] Preparata F., Shamos M., Computational Geometry. An introduction, Springer-Verlag, New York, 1985 | MR

[24] Prim R. C., “Shortest connecting networks and some generalizations”, BSTJ, 36 (1957), 1389–1401

[25] Rubinstein J. H., Thomas D. A., “The Steiner ratio conjecture for six points”, J. Combin. Thy. Ser. A58, 1989, 54–77 | MR

[26] Shamos M. I., Computational Geometry, Ph. D. Thesis, Dept. of Comput. Sci. Yale Univ., 1978

[27] Smith W. D., “How to find Steiner minimal trees in Euclidean $d$-space”, Algoritmica (to appear)

[28] Emelichev V. A. i dr., Lektsii po teorii grafov, Nauka, M., 1990 | MR | Zbl

[29] Dao Chong Tkhi, Fomenko A. T., Minimalnye poverkhnosti i problema Plato, Nauka, M., 1987 | MR | Zbl

[30] Fomenko A. T., Topologicheskie variatsionnye zadachi, Izd-vo MGU, M., 1984 | MR | Zbl

[31] Fomenko A. T., Variatsionnye metody v topologii, Nauka, M., 1982 | MR

[32] Tuzhilin A. A., Fomenko A. T., Elementy geometrii i topologii minimalnykh poverkhnostei, Nauka, M., 1991 | MR

[33] Ivanov A. O., Tuzhilin A. A., “Reshenie zadachi Shteinera dlya vypuklykh granits”, UMN, 45:2 (1990), 207–208 | MR | Zbl

[34] Ivanov A. O., Tuzhilin A. A., “Zadacha Shteinera dlya vypuklykh granits ili ploskie minimalnye seti”, Matem. sb., 182:12 (1991), 1813–1844 | MR

[35] Ivanov A. O., Tuzhilin A. A., “Geometriya minimalnykh setei i odnomernaya problema Plato”, UMN, 47:2 (1992), 53–115 | MR | Zbl

[36] Ivanov A. O., Tuzhilin A. A., “The Steiner problem for convex boundaries. I: general case”, Adv. Soviet Math., 15 (1993), 15–92 | MR | Zbl

[37] Ivanov A. O., Tuzhilin A. A., “The Steiner problem for convex boundaries. II: the regular case”, Adv. Soviet Math., 15 (1993), 93–131 | MR | Zbl

[38] Ivanov A. O., Tuzhilin A. A., Minimal Networks. The Steiner Problem and Its Generalizations, CRC Press, N.W., Boca Raton, Florida, 1994 | MR | Zbl

[39] Ivanov A. O., Tuzhilin A. A., “Topologii lokalno minimalnykh ploskikh binarnykh derevev”, UMN, 49:6 (1994), 191–192 | MR | Zbl

[40] Ivanov A. O., Tuzhilin A. A., “Vzveshennye minimalnye binarnye derevya”, UMN, 1995, no. 3, 155–156 | MR | Zbl

[41] Ivanov A. O., Iskhakov I. V., Tuzhilin A. A., “Minimalnye seti na pravilnykh mnogougolnikakh: realizatsiya lineinykh parketov”, Vestnik MGU. Ser. matem., 1993, no. 6, 77–80 | MR | Zbl

[42] Ivanov A. O., Ptitsyna I. V., Tuzhilin A. A., “Klassifikatsiya zamknutykh minimalnykh setei na ploskikh dvumernykh torakh”, Matem. sb., 183:12 (1992), 3–44 | MR | Zbl

[43] Shklyanko I. V., “Odnomernaya problema Plato na poverkhnostyakh”, Vestnik MGU. Ser. matem., 1989, no. 3, 8–11 | MR | Zbl

[44] Kuhn H. W., “Steiner's problem revisted”, In the book Studies in Optimization, Studies in Math., 10, eds. G. B. Dantzig, B. C. Eaves, Math. Assoc. Amer., 1975, 53–70 | MR

[45] Zacharias M., Encyklopädie der Mathematischen Wissenschaften, V. III AB9