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

Перейти к навигации Перейти к поиску
Строка 9: Строка 9:




Задача MST широко изучалась еще до формулировки задачи KKT; было разработано несколько эффективных детерминированных алгоритмов для ее решения. В основе всех этих детерминированных алгоритмов лежит метод, который жадным образом добавляет ребро к лесу, в любой момент представляющему собой подграф минимального остовного дерева. Ранние алгоритмы этого класса уже были достаточно эффективными: время исполнения составляло O(m log n). Среди них стоит упомянуть алгоритмы Борувки [ ], Ярника [8] (впоследствии переоткрытый Дейкстрой и Примом [ ]) и Крускала [5].
Задача MST широко изучалась еще до формулировки задачи KKT; было разработано несколько эффективных детерминированных алгоритмов для ее решения. В основе всех этих детерминированных алгоритмов лежит метод, который жадным образом добавляет ребро к лесу, в любой момент представляющему собой подграф минимального остовного дерева. Ранние алгоритмы этого класса уже были достаточно эффективными: время исполнения составляло O(m log n). Среди них стоит упомянуть алгоритмы Борувки [1], Ярника [8] (впоследствии переоткрытый Дейкстрой и Примом [5]) и Крускала [5].




Самый быстрый известный алгоритм MST до создания KKT исполнялся за время O(mlog/S(m, n)) [ ], где P(m, n) = minfijlog( и < m/и} [ ]; здесь log(i) n определяется как log n if i = 1 и как loglog^'"1' n if i > 1. Хотя это время исполнения близко к линейному, оно не является линейным в случае очень разреженных графов.
Самый быстрый известный алгоритм MST до создания KKT исполнялся за время <math>O(m \; log \; \beta (m, n))</math> [7], где <math>\beta (m, n) = min \{ i | log^{(i)} n \le m/n \}</math> [7]; здесь <math>log^{(i)} n \;</math> определяется как <math>log \; n</math>, если i = 1, и <math>log \; log^{(i - 1)} n \;</math>, если i > 1. Хотя это время исполнения близко к линейному, оно не является линейным в случае очень разреженных графов.




4551

правка

Навигация