Минимальные k-связные геометрические сети: различия между версиями

Первым результатом является расширение хорошо известного понятия о NP-полноте задачи нахождения 2-связной сети минимальной стоимости в графах общего вида (см., например, [10]) на геометрические сети.

'''Теорема 1. Задача нахождения 2-вершинно/реберно-связной геометрической сети минимальной стоимости, охватывающей набор из n точек на плоскости, является NPT-полной.'''

'''Теорема 2 ([6]). Существует константа <math>\xi > 0 \;</math>, такая, что задача аппроксимации 2-связной геометрической сети минимальной стоимости, охватывающей набор из n точек в <math>\mathbb{R}^{\lceil log_2 \; n \rceil}</math>, с коэффициентом <math>1 + \xi \;</math> является NP-полной.'''