Geodesic
Minimal spanning trees on infinite sets
Fundamentalʹnaâ i prikladnaâ matematika, Tome 20 (2015) no. 2, pp. 89-103 
A. O. Ivanov; A. A. Tuzhilin. Minimal spanning trees on infinite sets. Fundamentalʹnaâ i prikladnaâ matematika, Tome 20 (2015) no. 2, pp. 89-103. http://geodesic.mathdoc.fr/item/FPM_2015_20_2_a5/
@article{FPM_2015_20_2_a5,
     author = {A. O. Ivanov and A. A. Tuzhilin},
     title = {Minimal spanning trees on infinite sets},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {89--103},
     year = {2015},
     volume = {20},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_2015_20_2_a5/}
}
TY  - JOUR
AU  - A. O. Ivanov
AU  - A. A. Tuzhilin
TI  - Minimal spanning trees on infinite sets
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2015
SP  - 89
EP  - 103
VL  - 20
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/FPM_2015_20_2_a5/
LA  - ru
ID  - FPM_2015_20_2_a5
ER  - 
%0 Journal Article
%A A. O. Ivanov
%A A. A. Tuzhilin
%T Minimal spanning trees on infinite sets
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2015
%P 89-103
%V 20
%N 2
%U http://geodesic.mathdoc.fr/item/FPM_2015_20_2_a5/
%G ru
%F FPM_2015_20_2_a5

Voir la notice de l'article provenant de la source Math-Net.Ru

Minimal spanning trees on infinite vertex sets are investigated. A criterion for minimality of a spanning tree having a finite length is obtained, which generalizes the corresponding classical result for finite sets. It is given an analytic description of the set of all infinite metric spaces which a minimal spanning tree exists for. A sufficient condition for a minimal spanning tree existence is obtained in terms of distance achievability between elements of a partition of the metric space under consideration. Besides, a concept of a locally minimal spanning tree is introduced, several properties of such trees are described, and relations of those trees with (globally) minimal spanning trees are investigated.

[1] Ivanov A. O., Nikonov I. M., Tuzhilin A. A., “Mnozhestva, dopuskayuschie soedinenie grafami konechnoi dliny”, Mat. sb., 196:6 (2005), 71–110 | DOI | MR | Zbl

[2] Aldous D., Steele J. M., “Asymptotics for Euclidean minimal spanning trees on random points”, Probab. Theory Relat. Fields, 92 (1992), 247–258 | DOI | MR | Zbl

[3] Alexander K. S., “Percolation and minimal spanning forests in infinite graphs”, Ann. Probab., 23:1 (1995), 87–104 | DOI | MR | Zbl

[4] Borůvka O., “O jistém problému minimálním”, Práce Mor. Prírodoved. Spol. v Brne (Acta Soc. Sci. Nat. Moravicae), 3 (1926), 37–58 | Zbl

[5] Ivanov A., Tuzhilin A., “The Steiner ratio Gilbert–Pollak conjecture is still open”, Algorithmica, 62:1–2 (2012), 630–632 | DOI | MR | Zbl

[6] Preparata F. P., Shamos M. I., Computational Geometry, an Introduction, Springer, Berlin, 1985 | MR | Zbl

[7] Shamos M. I., Computational Geometry, Ph. D. Thesis, Yale Univ., 1978

[8] Smith W. D., Smith J. M., “On the Steiner ratio in $3$-space”, J. Combin. Theory A, 65 (1995), 301–322 | DOI | MR