4551
правка
Минимальные k-связные геометрические сети: различия между версиями
Перейти к навигации
Перейти к поиску
Минимальные k-связные геометрические сети (посмотреть исходный код)
Версия от 17:19, 15 сентября 2016
, 15 сентября 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 104: | Строка 104: | ||
Теорема 7 (Схемы аппроксимации для 2-связных графов, [5]). Пусть d – любое целое число, d > 2, а " – любое положительное вещественное число. Пусть S – множество из n точек в пространстве Rd. Существует рандомизированный алгоритм, который за время n ■ log n • (d/")O(d) с вероятностью не менее 0,99 находит 2-вершинно-связную (или 2-реберно-связную) остовную сеть для S, стоимость которой не больше чем в (1 + ") раз превышает оптимальную. Этот алгоритм может быть дерандомизирован за полиномиальное время. | |||
Для константного значения d время выполнения рандомизированных алгоритмов составляет nlog n • (1/")O(1) + 2(1/")O(1). | |||
Теорема 8 ([7]). Пусть d – любое целое число, d > 2, а " – любое положительное вещественное число. Пусть S – множество из n точек в пространстве Rd. Существует рандомизированный алгоритм, который за время n ■ log n • (d/")O(d) + n-2{dls)°{i2) + n-22i с вероятностью не менее 0,99 находит 2-вершинно-связную (или 2-реберно-связную) остовную сеть Штейнера для S, стоимость которой не больше чем в (1 + ") раз превышает оптимальную. Этот алгоритм может быть дерандомизирован за полиномиальное время. | |||
Теорема 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. Этот алгоритм может быть дерандомизирован за полиномиальное время. | |||
== Применение == | |||
Multi-connectivity problems are central in algorithmic graph theory and have numerous applications in computer science and operation research, see, e.g., [1,13, 11,18]. They also play very important role in the design of networks that arise in practical situations, see, e.g., [1,13]. Typical application areas include telecommunication, computer and road networks. Low degree connectivity problems for geometrical networks in the plane can often closely approximate such practical connectivity problems (see, e.g., the discussion in [13,17,18]). The survivable network design problem in geometric networks also arises in many applications, e. g., in telecommunication, communication network design, VLSI design, etc. [12,13,17,18]. | Multi-connectivity problems are central in algorithmic graph theory and have numerous applications in computer science and operation research, see, e.g., [1,13, 11,18]. They also play very important role in the design of networks that arise in practical situations, see, e.g., [1,13]. Typical application areas include telecommunication, computer and road networks. Low degree connectivity problems for geometrical networks in the plane can often closely approximate such practical connectivity problems (see, e.g., the discussion in [13,17,18]). The survivable network design problem in geometric networks also arises in many applications, e. g., in telecommunication, communication network design, VLSI design, etc. [12,13,17,18]. | ||