4628
правок
Параллельные алгоритмы вычисления компонент связности и минимальных остовных деревьев: различия между версиями
Перейти к навигации
Перейти к поиску
м
Параллельные алгоритмы вычисления компонент связности и минимальных остовных деревьев (посмотреть исходный код)
Версия от 13:45, 27 марта 2016
, 27 марта 2016→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Алгоритмы EREW PRAM для нахождения компонент связности и миним…») |
Irina (обсуждение | вклад) |
||
| Строка 4: | Строка 4: | ||
== Постановка задачи == | == Постановка задачи == | ||
Пусть дан взвешенный неориентированный граф G с n вершинами и m ребрами. Необходимо вычислить минимальное остовное дерево (или остовный лес) графа G на параллельной машине с произвольным доступом к памяти (parallel random access machine, PRAM) без возможности одновременной записи. | Пусть дан взвешенный неориентированный граф G с n вершинами и m ребрами. Необходимо вычислить [[минимальное остовное дерево]] (или остовный лес) графа G на параллельной машине с произвольным доступом к памяти (parallel random access machine, PRAM) без возможности одновременной записи. | ||
| Строка 11: | Строка 11: | ||
Предполагается, что входной граф G представлен в виде списков смежности. Изолированные вершины (имеющие степень 0) удаляются, в результате чего предполагается, что m > n. | Предполагается, что входной граф G представлен в виде списков смежности. Изолированные вершины (имеющие степень 0) удаляются, в результате чего предполагается, что m > n. | ||
== Основные результаты == | == Основные результаты == | ||