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

Пусть дан взвешенный неориентированный граф G с n вершинами и m ребрами. Необходимо вычислить [[минимальное остовное дерево]] (или остовный лес) графа G на [[PRAM|параллельной равнодоступной машине]] (parallel random access machine, PRAM) без возможности одновременной записи.

Минимальное остовное дерево графа представляет собой остовное дерево с минимальной возможной суммой весов ребер. Параллельная машина с произвольным доступом к памяти (PRAM) – это абстрактная модель для разработки параллельных алгоритмов и понимания возможностей параллелизма. В этой модели процессоры (каждый из которых является машиной с произвольным доступом к памяти) работают синхронно, обмениваясь друг с другом сообщениями при помощи совместно используемой памяти. PRAM можно различать по тому обстоятельству, разрешается ли более чем одному процессору одновременно производить операции чтения и записи с одной и той же ячейкой совместно используемой памяти. Более строгой является модель с одновременным чтением и одновременной записью CRCW (concurrent-read, concurrent-write), более слабой – с эксклюзивным чтением и эксклюзивной записью, EREW (exclusive-read, exclusive-write). Введение в алгоритмы PRAM см. в работах Карпа и Рамачандрана [8] и Джаджи [5].