4551
правка
Рандомизированный алгоритм нахождения минимального остовного дерева: различия между версиями
Перейти к навигации
Перейти к поиску
м
Рандомизированный алгоритм нахождения минимального остовного дерева (посмотреть исходный код)
Версия от 23:34, 16 апреля 2016
, 16 апреля 2016→Контекст и история
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 22: | Строка 22: | ||
• Основной компонент алгоритма Борувки [1] – «шаг Борувки», который выбирает ребро с минимальным весом, инцидентное каждой вершине, добавляет его к минимальному остовному дереву и затем выполняет сжатие данных ребер. Этот шаг выполняется за линейное время и поддается эффективному распараллеливанию. Он стал основой для самых эффективных параллельных алгоритмов поиска минимального остовного дерева; этот подход также используется алгоритмом KKT. | • Основной компонент алгоритма Борувки [1] – «шаг Борувки», который выбирает ребро с минимальным весом, инцидентное каждой вершине, добавляет его к минимальному остовному дереву и затем выполняет сжатие данных ребер. Этот шаг выполняется за линейное время и поддается эффективному распараллеливанию. Он стал основой для самых эффективных параллельных алгоритмов поиска минимального остовного дерева; этот подход также используется алгоритмом KKT. | ||
• Родственная и более простая задача касается верификации минимального остовного дерева. В этой задаче имеется остовное дерево T для входного графа со взвешенными ребрами и необходимо определить, является ли оно минимальным. Алгоритм, решающий эту задачу при помощи линейного количества сравнений весов ребер, бал предложен Комлошем [ ]; позднее был разработан детерминированный алгоритм с линейным временем исполнения [6] (см. также более простой алгоритм в [12]). | • Родственная и более простая задача касается верификации минимального остовного дерева. В этой задаче имеется остовное дерево T для входного графа со взвешенными ребрами и необходимо определить, является ли оно минимальным. Алгоритм, решающий эту задачу при помощи линейного количества сравнений весов ребер, бал предложен Комлошем [13]; позднее был разработан детерминированный алгоритм с линейным временем исполнения [6] (см. также более простой алгоритм в [12]). | ||
== Основные результаты == | == Основные результаты == | ||