Research indexJournal article
Расстояния Громова — Хаусдорфа до симплексов и некоторые приложения к дискретной оптимизации
Ivanov, Тужилин
Чебышевский сборник12 Mar 2020Open access
NobleIDark:/48914/w1/20260515/16015084DOI10.22405/2226-8383-2020-21-2-169-189
Расстояния Громова — Хаусдорфа до симплексов и некоторые приложения к дискретной оптимизации
Ivanov, Тужилин · Чебышевский сборник · 2020
NobleIDark:/48914/w1/20260515/16015084DOI10.22405/2226-8383-2020-21-2-169-189
Abstract
В работе изучается взаимосвязь между расстоянием Громова — Хаусдорфа и задачами дискретной оптимизации. Расстояние Громова — Хаусдорфа до метрического пространства с одинаковыми непутевыми расстояниями используется используется для решения следующих проблем: вычисление длин ребер минимального остовного дерева для конечного метрического пространства; обобщенная пробам Борсука; вычисление хроматическогочисла и минимального размера клинкового покрытия для простого графа.