Open AccessРасстояния Громова — Хаусдорфа до симплексов и некоторые приложения к дискретной оптимизации
Author(s) -
Alexandr Olegovich Ivanov,
A. A. Tuzhilin
Publication year - 2020
Publication title -
čebyševskij sbornik
Language(s) - Russian
Resource type - Journals
SCImago Journal Rank - 0.273
H-Index - 6
eISSN - 2587-7119
pISSN - 2226-8383
DOI - 10.22405/2226-8383-2020-21-2-169-189
Subject(s) - computer science
В работе изучается взаимосвязь между расстоянием Громова — Хаусдорфа и задачами дискретной оптимизации. Расстояние Громова — Хаусдорфа до метрического пространства с одинаковыми непутевыми расстояниями используется используется для решения следующих проблем: вычисление длин ребер минимального остовного дерева для конечного метрического пространства; обобщенная пробам Борсука; вычисление хроматическогочисла и минимального размера клинкового покрытия для простого графа.