Рандомизированный алгоритм нахождения минимального остовного дерева: различия между версиями

Теорема 2. Алгоритм KKT представляет собой рандомизированный алгоритм, вычисляющий минимальное остовное дерево неориентированного графа с n вершин и m взвешенных ребер за время O(n + m) с вероятностью не менее 1 — exp (— Q{m)). Ожидаемое время исполнения составляет O(n + m), а в наихудшем случае – O(m + n log n).

В качестве модели вычислений в [ ] использовалась RAM-модель с единичной стоимостью, поскольку известные алгоритмы верификации минимального остовного дерева были разработаны именно для этой модели, а не для более ограничивающей модели машины с указателями. Впоследствии было показано, что результат верификации МОД и, следовательно, алгоритм KKT работают также и для машины с указателями [2].

Лемма 1 была доказана в [ ] при помощи моделирования алгоритма Крускала и анализа вероятности того, что F-легкое ребро не будет выбрано. Еще одно доказательство, использующее обратный анализ, приведено в [ ].