|
КЛАССИФИКАТОР: метрическая геометрия
АВТОРЫ:
Тужилин А.А.
(A. A. Tuzhilin)
Вычисление длин ребер минимальных остовных деревьев через расстояния
Громова-Хаусдорфа.
(Calculation of Minimum Spanning Tree Edges Lengths using
Gromov-Hausdorff Distance.)
АННОТАЦИЯ:
В работе показывается, как можно вычислить длины ребер минимального
остовного дерева конечного метрического пространства через
расстояния Громова-Хаусдорфа от этого пространства до симплексов с
достаточно длинной стороной. Здесь под симплексами мы понимаем
конечные метрические пространства, все ненулевые расстояний в
которых одинаковы. В качестве приложения мы сводим задачу поиска
минимального дерева Штейнера и минимального заполнения к
максимизации суммарного расстояния до некоторого набора симплексов в
пространстве Громова-Хаусдорфа.
In the present paper we show how one can calculate the lengths of
edges of a minimum spanning tree constructed for a finite metric
space, in terms of the Gromov-Hausdorff distances from this space to
simplices of sufficiently large diameter. Here by simplices we mean
finite metric spaces all of whose nonzero distances are the same. As
an application, we reduce the problems of finding a Steiner minimal
tree length or a minimal filling length to maximization of the total
distance to some finite number of simplices considered as points of
the Gromov-Hausdorff space.
Ссылка на статью
|
|
|
О проекте