Алгоритм DCSC поиска компонент сильной связности

Материал из Алговики
Версия от 22:16, 6 июня 2015; Daryin (обсуждение | вклад) (Общее описание алгоритма)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к навигации Перейти к поиску

1 Свойства и структура алгоритмов

Алгоритм DCSC[1][2][3] (англ. Divide and Conquer Strong Components – компоненты сильной связности по принципу «Разделяй и властвуй») находит компоненты сильной связности ориентированного графа с ожидаемой работой [math]O(n \ln n)[/math] (при условии ограниченной степени вершин).

1.1 Общее описание алгоритма

1.2 Математическое описание

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Описание схемы реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

Ожидаемая последовательная сложность алгоритма составляет [math]O(n \ln n)[/math] при условии, что степень вершин ограничена сверху константой.

1.7 Информационный граф

1.8 Описание ресурса параллелизма алгоритма

Алгоритм изначально предназначен для параллельной реализации: на каждом шаге он находит одну компоненту сильной связности и выделяет до трёх подмножеств графа, которые содержат другие компоненты связности и могут обрабатываться параллельно. Алгоритм не подходит для графов, в которых имеется малое число компонент сильной связности, так как ход исполнения алгоритма в этом случае фактически является последовательным.

1.9 Описание входных и выходных данных

1.10 Свойства алгоритма

2 Программная реализация алгоритмов

2.1 Особенности реализации последовательного алгоритма

2.2 Описание локальности данных и вычислений

2.3 Возможные способы и особенности реализации параллельного алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

3 Литература

  1. ↑ Fleischer, Lisa K, Bruce Hendrickson, and Ali Pınar. “On Identifying Strongly Connected Components in Parallel.” In Lecture Notes in Computer Science, Volume 1800, Springer, 2000, pp. 505–11. doi:10.1007/3-540-45591-4_68.
  2. ↑ McLendon, William, III, Bruce Hendrickson, Steven J Plimpton, and Lawrence Rauchwerger. “Finding Strongly Connected Components in Distributed Graphs.” Journal of Parallel and Distributed Computing 65, no. 8 (August 2005): 901–10. doi:10.1016/j.jpdc.2005.03.007.
  3. ↑ Hong, Sungpack, Nicole C Rodia, and Kunle Olukotun. “On Fast Parallel Detection of Strongly Connected Components (SCC) in Small-World Graphs,” Proceeedings of SC'13, 1–11, New York, New York, USA: ACM Press, 2013. doi:10.1145/2503210.2503246.
Источник — https://algowiki-project.org/w/ru/index.php?title=Алгоритм_DCSC_поиска_компонент_сильной_связности&oldid=1755