4551
правка
Минимальные k-связные геометрические сети: различия между версиями
Перейти к навигации
Перейти к поиску
м
Минимальные k-связные геометрические сети (посмотреть исходный код)
Версия от 22:33, 15 сентября 2016
, 15 сентября 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 61: | Строка 61: | ||
== Основные результаты == | == Основные результаты == | ||
Первым результатом является расширение хорошо известного понятия о NP-полноте задачи 2-связной сети минимальной стоимости в графах общего вида (см., например, [ ]) на геометрические сети. | Первым результатом является расширение хорошо известного понятия о NP-полноте задачи нахождения 2-связной сети минимальной стоимости в графах общего вида (см., например, [ ]) на геометрические сети. | ||
| Строка 75: | Строка 75: | ||
Теорема 3 ([6]). Для целого числа d > log n и любого фиксированного p > 1 существует константа £ > 0, такая, что задача аппроксимации 2-связной сети минимальной стоимости, охватывающей набор из n точек в метрике lp в пространстве Rd, с коэффициентом 1 + % является NP-полной. | Теорема 3 ([6]). Для любого целого числа d > log n и любого фиксированного p > 1 существует константа £ > 0, такая, что задача аппроксимации 2-связной сети минимальной стоимости, охватывающей набор из n точек в метрике lp в пространстве Rd, с коэффициентом 1 + % является NP-полной. | ||