|
Fundamentalnaya i Prikladnaya Matematika, 2015, Volume 20, Issue 2, Pages 89–103
(Mi fpm1642)
|
|
|
|
Minimal spanning trees on infinite sets
A. O. Ivanov, A. A. Tuzhilin Lomonosov Moscow State University
Abstract:
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.
Citation:
A. O. Ivanov, A. A. Tuzhilin, “Minimal spanning trees on infinite sets”, Fundam. Prikl. Mat., 20:2 (2015), 89–103; J. Math. Sci., 223:6 (2017), 711–719
Linking options:
https://www.mathnet.ru/eng/fpm1642 https://www.mathnet.ru/eng/fpm/v20/i2/p89
|
Statistics & downloads: |
Abstract page: | 260 | Full-text PDF : | 138 | References: | 52 |
|