4501
правка
Алгоритмы поиска остова во взвешенном графе: различия между версиями
Перейти к навигации
Перейти к поиску
м
Алгоритмы поиска остова во взвешенном графе (посмотреть исходный код)
Версия от 14:36, 17 июля 2014
, 17 июля 2014→Алгоритм II
Irina (обсуждение | вклад) м (→Алгоритм I) |
Irina (обсуждение | вклад) м (→Алгоритм II) |
||
| Строка 30: | Строка 30: | ||
Пусть даны взвешенный граф G = (V, E) и целое число k > 1. Остов с коэффициентом растяжения (2k–1) и размером <math>O(kn^{1+\frac{1}{k}})</math> может быть вычислен за время O(km). | Пусть даны взвешенный граф G = (V, E) и целое число k > 1. Остов с коэффициентом растяжения (2k–1) и размером <math>O(kn^{1+\frac{1}{k}})</math> может быть вычислен за время O(km). | ||
Алгоритм выполняется в O(k) этапов; на каждом этапе он вычисляет список смежности для каждой вершины с целью отсечения необязательных | Алгоритм выполняется в O(k) этапов; на каждом этапе он вычисляет список смежности для каждой вершины с целью отсечения необязательных ребер. Для доказательства простоты алгоритма далее приводятся его полная версия для нахождения 3-остова и анализ алгоритма. Алгоритм может быть легко адаптирован к другим вычислительным моделям (с параллельной, внешней или распределенной памятью) с сохранением почти оптимальной производительности (подробнее см. в [6]). | ||
== Вычисление 3-остова за линейное время == | == Вычисление 3-остова за линейное время == | ||