Geodesic
Stabilization of a locally minimal forest
Sbornik. Mathematics, Tome 205 (2014) no. 3, pp. 387-418 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The method of partial stabilization of locally minimal networks, which was invented by Ivanov and Tuzhilin to construct examples of shortest trees with given topology, is developed. According to this method, boundary vertices of degree $2$ are not added to all edges of the original locally minimal tree, but only to some of them. The problem of partial stabilization of locally minimal trees in a finite-dimensional Euclidean space is solved completely in the paper, that is, without any restrictions imposed on the number of edges remaining free of subdivision. A criterion for the realizability of such stabilization is established. In addition, the general problem of searching for the shortest forest connecting a finite family of boundary compact sets in an arbitrary metric space is formalized; it is shown that such forests exist for any family of compact sets if and only if for any finite subset of the ambient space there exists a shortest tree connecting it. The theory developed here allows us to establish further generalizations of the stabilization theorem both for arbitrary metric spaces and for metric spaces with some special properties. Bibliography: 10 titles.
Keywords: metric spaces, locally minimal trees, minimal Steiner trees, shortest trees, shortest forests, stabilization of a locally minimal tree. 
@article{SM_2014_205_3_a3,
     author = {A. O. Ivanov and A. E. Mel'nikova and A. A. Tuzhilin},
     title = {Stabilization of a~locally minimal forest},
     journal = {Sbornik. Mathematics},
     pages = {387--418},
     year = {2014},
     volume = {205},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2014_205_3_a3/}
}
TY  - JOUR
AU  - A. O. Ivanov
AU  - A. E. Mel'nikova
AU  - A. A. Tuzhilin
TI  - Stabilization of a locally minimal forest
JO  - Sbornik. Mathematics
PY  - 2014
SP  - 387
EP  - 418
VL  - 205
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/SM_2014_205_3_a3/
LA  - en
ID  - SM_2014_205_3_a3
ER  - 
%0 Journal Article
%A A. O. Ivanov
%A A. E. Mel'nikova
%A A. A. Tuzhilin
%T Stabilization of a locally minimal forest
%J Sbornik. Mathematics
%D 2014
%P 387-418
%V 205
%N 3
%U http://geodesic.mathdoc.fr/item/SM_2014_205_3_a3/
%G en
%F SM_2014_205_3_a3
A. O. Ivanov; A. E. Mel'nikova; A. A. Tuzhilin. Stabilization of a locally minimal forest. Sbornik. Mathematics, Tome 205 (2014) no. 3, pp. 387-418. http://geodesic.mathdoc.fr/item/SM_2014_205_3_a3/

[1] V. Jarník, M. Kössler, “O minimalnich grafeth obeahujicich n danijch bodu”, Časopis Pěst. Mat., 63 (1934), 223–235 | Zbl

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

[3] M. R. Garey, R. L. Graham, D. S. Johnson, “Some NP-complete geometric problems”, Proceedings of the eighth annual ACM symposium on Theory of computing (Hershey, Pa., 1976), ACM, New York, NY, 1976, 10–22 | MR | Zbl

[4] A. O. Ivanov, A. A. Tuzhilin, “Stabilization of locally minimal trees”, Math. Notes, 86:3-4 (2009), 483–492 | DOI | DOI | MR | Zbl

[5] A. O. Ivanov, O. A. S'edina, A. A. Tuzhilin, “The structure of minimal Steiner trees in the neighborhoods of the lunes of their edges”, Math. Notes, 91:3-4 (2012), 339–353 | DOI | DOI

[6] N. P. Strelkova, “Ustoichivost lokalno minimalnykh setei”, Tr. sem. po vekt. i tenz. analizu, 29 (2013), 148–170

[7] A. O. Ivanov, A. A. Tuzhilin, Teoriya ekstremalnykh setei, Institut kompyuternykh issledovanii, M.–Izhevsk, 2003, 424 pp.

[8] D. Yu. Burago, Yu. D. Burago, S. V. Ivanov, Kurs metricheskoi geometrii, Institut kompyuternykh issledovanii, M.–Izhevsk, 2004, 512 pp.

[9] A. O. Ivanov, A. A. Tuzhilin, Minimal networks. The Steiner problem and its generalizations, CRC Press, Boca Raton, FL, 1994, xviii+414 pp. | MR | Zbl

[10] B. B. Bednov, N. P. Strelkova, “On the existence of shortest networks in Banach spaces”, Math. Notes, 94:1 (2013), 41–48 | DOI | DOI | Zbl