4551
правка
Минимальные k-связные геометрические сети: различия между версиями
Материал из WEGA
Минимальные k-связные геометрические сети (посмотреть исходный код)
Версия от 14:50, 15 сентября 2016
, 15 сентября 2016→Основные результаты
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 61: | Строка 61: | ||
== Основные результаты == | == Основные результаты == | ||
Первым результатом является расширение хорошо известного понятия о NP-полноте задачи 2-связной сети минимальной стоимости в графах общего вида (см., например, [ ]) на геометрические сети. | |||
Теорема 1. Задача нахождения 2-вершинно/реберно-связной геометрической сети минимальной стоимости, охватывающей набор из n точек на плоскости, является NPT-полной. | |||
Следующий результат показывает, что если рассматривать задачи о многосвязности с нахождением объектов минимальной стоимости для достаточно большой размерности, эти задачи становятся APX-полными. | |||
Теорема 2 ([6]). Существует константа £ > 0, такая, что задача аппроксимации 2-связной геометрической сети минимальной стоимости, охватывающей набор из n точек в Rdlog2ne, с коэффициентом 1 + % является NPT-полной. | |||
Этот результат также можно расширить на любую lp-норму. | |||
Theorem 3 ([6]) For and integer d > log n and for any fixed p > 1 there exists a constant f > 0 such that it is NP-hard to approximate within 1 + f the minimum-cost 2-connected network spanning a set of n points in the lp metric in Rd. | Theorem 3 ([6]) For and integer d > log n and for any fixed p > 1 there exists a constant f > 0 such that it is NP-hard to approximate within 1 + f the minimum-cost 2-connected network spanning a set of n points in the lp metric in Rd. | ||
