Главная    Ex Libris    Книги    Журналы    Статьи    Серии    Каталог    Wanted    Загрузка    ХудЛит    Справка    Поиск по индексам    Поиск    Форум   
blank
Разделы

square Читателям

square Авторам

square Статьи

blank
Авторизация

       
blank
Поиск по указателям

blank
Красота
blank
blank
Электронный журнал

КЛАССИФИКАТОР: метрическая геометрия

АВТОРЫ:

Тужилин А.А.

(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.

Ссылка на статью
blank
Редколлегия
Главный редактор:
д. ф-м. н., проф., Чубариков В.Н.
Зам. главного редактора:
д. ф-м. н., проф., Мищенко А.С.
blank
HR
© Электронная библиотека попечительского совета мехмата МГУ, 2004-2017
Электронная библиотека мехмата МГУ | Valid HTML 4.01!| Valid CSS! О проекте