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

Теорема 5 (PTAS для вершинной или реберной связности [6, 5]). Пусть d > 2 – любое константное целое число. Существует определенная положительная константа c < 1, такая, что для всех k < (loglogn)c задачи построения k-вершинно-связной или k-реберно-связной остовной сети минимальной стоимости для множества точек в пространстве Rd допускают использование PTAS.

Теорема 9 ([7]). Пусть d – любое целое число, d > 2, а " – любое положительное вещественное число. Пусть S – множество из n точек в пространстве Rd. Существует рандомизированный алгоритм, который за время n ■ log n • (d/")O(d) + n-2ldle)°(d ) + n-22d с вероятностью не менее 0,99 решает задачу построения геометрической сети с повышенной живучестью с rv 2 f0; 1; 2g для любого v 2 V. Этот алгоритм может быть дерандомизирован за полиномиальное время.