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

Задача нахождения минимального остовного дерева (MST) связана с задачей нахождения [[компонента связности|компоненты связности]] (CC) неориентированного графа. Последовательные алгоритмы решения задач CC и MST за время O(m) и O(m log n), соответственно, известны уже несколько десятилетий. Также было предложено несколько более эффективных алгоритмов MST, в том числе недавний алгоритм Петти-Рамачандрана [9], являющийся доказуемо оптимальным.

В параллельном контексте эти задачи решаются сходным образом. В случае CRCW обе задачи можно решить за время O(log n) при помощи n + m процессоров (см, например, Коул и Вишкин [3]). Используя рандомизацию, можно ограничиться для решения (n + m)/log n процессорами с ожидаемым временем исполнения O(log n) [2, 10].

В случае EREW PRAM для решения задач CC и MST в начале восьмидесятых были разработаны алгоритмы с временем исполнения O(log2 n). Некоторое время считалось, что для моделей с эксклюзивной записью (как для случая одновременного чтения, так и для эксклюзивного) невозможно улучшить временную границу O(log n) [ ]. Первый прорыв совершили Джонсон и Метаксас [6], предложившие алгоритмы с временем исполнения O(log1:5 n) для обеих задач. Чонг и Лэм вскоре улучшили этот результат до O(log n log log n). Если допускается рандомизация, то временная сложность может быть уменьшена до ожидаемого времени O(log n) в оптимальном случае [7,10,11]. Наконец, Чонг, Хан и Лэм [1] получили алгоритм для задач MST и CC с временем исполнения O(log n) для n + m процессоров, не требующий рандомизации. Заметим, что время @(log n) является оптимальным, поскольку данные графовые задачи имеют не меньшую сложность, чем выполнение операции OR для n бит, для которой Кук и коллеги [4] показали, что она требует J2(log n) времени для PRAM с эксклюзивной записью, независимо от количества используемых процессоров.