4551
правка
Минимальные k-связные геометрические сети: различия между версиями
Перейти к навигации
Перейти к поиску
м
Минимальные k-связные геометрические сети (посмотреть исходный код)
Версия от 14:50, 15 сентября 2016
, 15 сентября 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 65: | Строка 65: | ||
Теорема 1. Задача нахождения 2-вершинно/реберно-связной геометрической сети минимальной стоимости, охватывающей набор из n точек на плоскости, является NPT-полной. | Теорема 1. Задача нахождения 2-вершинно/реберно-связной геометрической сети минимальной стоимости, охватывающей набор из n точек на плоскости, является NPT-полной. | ||
Следующий результат показывает, что если рассматривать задачи о многосвязности с нахождением объектов минимальной стоимости для достаточно большой размерности, эти задачи становятся APX-полными. | Следующий результат показывает, что если рассматривать задачи о многосвязности с нахождением объектов минимальной стоимости для достаточно большой размерности, эти задачи становятся APX-полными. | ||