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

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