Расстояния Громова — Хаусдорфа до симплексов и некоторые приложения к дискретной оптимизации
https://doi.org/10.22405/2226-8383-2020-21-2-169-189
Аннотация
В работе изучается взаимосвязь между расстоянием Громова — Хаусдорфа и задачами дискретной оптимизации. Расстояние Громова — Хаусдорфа до метрического пространства с одинаковыми непутевыми расстояниями используется используется для решения следующих проблем: вычисление длин ребер минимального остовного дерева для конечного метрического пространства; обобщенная пробам Борсука; вычисление хроматического
числа и минимального размера клинкового покрытия для простого графа.
Об авторах
Александр Олегович Иванов
Московский государственный университет имени М. В. Ломоносова;
Московский государственный технический университет имени Н. Э. Баумана
Россия
Россия
профессор
Алексей Августинович Тужилин
Московский государственный университет имени М. В. Ломоносова
Россия
Россия
профессор, механико-математический факультет
Рецензия
Для цитирования:
Иванов А.О., Тужилин А.А. Расстояния Громова — Хаусдорфа до симплексов и некоторые приложения к дискретной оптимизации. Чебышевский сборник. 2020;21(2):169-189. https://doi.org/10.22405/2226-8383-2020-21-2-169-189
For citation:
Ivanov A.O., Tuzhilin A.A. Gromov–Hausdorff Distances to Simplexes and Some Applications to Discrete Optimisation. Chebyshevskii Sbornik. 2020;21(2):169-189. https://doi.org/10.22405/2226-8383-2020-21-2-169-189
Просмотров: 369
Послать статью по эл. почте 