Geodesic
Sets admitting connection by graphs of finite length
Sbornik. Mathematics, Tome 196 (2005) no. 6, pp. 845-884 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The aim of this paper is the description and study of the properties of the subsets $M$ of a metric space $\mathbb X$ that can be connected by a graph of finite length. We obtain a criterion describing these sets, find several geometric properties of them (in the case $\mathbb X=\mathbb R^n$), and derive a formula for calculating the length of a minimal spanning tree on $M\subset\mathbb X$ as the integral of a certain function constructed by $M$. 
@article{SM_2005_196_6_a3,
     author = {A. O. Ivanov and I. M. Nikonov and A. A. Tuzhilin},
     title = {Sets admitting connection by graphs of finite length},
     journal = {Sbornik. Mathematics},
     pages = {845--884},
     year = {2005},
     volume = {196},
     number = {6},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2005_196_6_a3/}
}
TY  - JOUR
AU  - A. O. Ivanov
AU  - I. M. Nikonov
AU  - A. A. Tuzhilin
TI  - Sets admitting connection by graphs of finite length
JO  - Sbornik. Mathematics
PY  - 2005
SP  - 845
EP  - 884
VL  - 196
IS  - 6
UR  - http://geodesic.mathdoc.fr/item/SM_2005_196_6_a3/
LA  - en
ID  - SM_2005_196_6_a3
ER  - 
%0 Journal Article
%A A. O. Ivanov
%A I. M. Nikonov
%A A. A. Tuzhilin
%T Sets admitting connection by graphs of finite length
%J Sbornik. Mathematics
%D 2005
%P 845-884
%V 196
%N 6
%U http://geodesic.mathdoc.fr/item/SM_2005_196_6_a3/
%G en
%F SM_2005_196_6_a3
A. O. Ivanov; I. M. Nikonov; A. A. Tuzhilin. Sets admitting connection by graphs of finite length. Sbornik. Mathematics, Tome 196 (2005) no. 6, pp. 845-884. http://geodesic.mathdoc.fr/item/SM_2005_196_6_a3/

[1] Ivanov A. O., Tuzhilin A. A., Teoriya ekstremalnykh setei, Institut kompyuternykh issledovanii, Moskva, Izhevsk, 2003

[2] Fermat P., Abhandlungen über Maxima und Minima, Academische Verlagsgesellschaft, Leipzig, 1934

[3] Garey M. R., Graham R. L., Johnson D. S., “Some $NP$-complete geometric problems”, Eighth annual symp. on theory of comput. (Hershey, PA, USA), ACM Press, New York, 1976, 10–22 | MR | Zbl

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

[5] 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

[6] Prim R. C., “Shortest connecting networks and some generalizations”, Bell Syst. Tech. J., 36 (1957), 1389–1401

[7] Delaunay B., “Sur la sphère vide”, Bull. Acad. Sci. USSR (7), 1934, no. 6, 793–800 | Zbl

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

[9] Cieslik D., The Steiner ratio, Kluwer Acad. Publ., Boston, 2001 | MR | Zbl

[10] 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 31st annual symp. on found. of comput. sci., v. 1 (22.10.90–24.10.90, St. Louis, MO, USA), 1990, 76–85 | MR

[11] Du D. Z., Hwang F. K., “A proof of Gilbert–Pollak conjecture on the Steiner ratio”, Algorithmica, 7 (1992), 121–135 | DOI | MR | Zbl

[12] Du D. Z., Smith W. D., “Disproofs of generalized Gilbert–Pollak conjecture on the Steiner ratio in three or more dimensions”, J. Combin. Theory. Ser. A, 74 (1996), 115–130 | DOI | MR | Zbl

[13] Smith W. D., Smith J. M., “On the Steiner ration in 3-space”, J. Combin. Theory. Ser. A, 65 (1995), 301–332 | DOI | MR

[14] Toppur B., Smith J. M., “Properties of $\mathcal R$-Sausages”, Discrete Comput. Geom., 31 (2004), 587–611 | MR | Zbl

[15] Jain A. K., Dubes R. C., Algorithms for clustering data, Prentice Hall, Englewood Cliffs, NJ, 1988 | MR | Zbl