Алгоритм DCSC поиска компонент сильной связности
Свойства и структура алгоритмов
Общее описание алгоритма
Алгоритм DCSC[1][2][3] (англ. Divide and Conquer Strong Components – компоненты сильной связности по принципу «Разделяй и властвуй») находит компоненты сильной связности ориентированного графа с ожидаемой работой [math]\displaystyle{ O(n \ln n) }[/math] (при условии ограниченной степени вершин).
Математическое описание
Вычислительное ядро алгоритма
Макроструктура алгоритма
Описание схемы реализации последовательного алгоритма
Последовательная сложность алгоритма
Ожидаемая последовательная сложность алгоритма составляет [math]\displaystyle{ O(n \ln n) }[/math] при условии, что степень вершин ограничена сверху константой.
Информационный граф
Описание ресурса параллелизма алгоритма
Алгоритм изначально предназначен для параллельной реализации: на каждом шаге он находит одну компоненту сильной связности и выделяет до трёх подмножеств графа, которые содержат другие компоненты связности и могут обрабатываться параллельно. Алгоритм не подходит для графов, в которых имеется малое число компонент сильной связности, так как ход исполнения алгоритма в этом случае фактически является последовательным.
Описание входных и выходных данных
Свойства алгоритма
Программная реализация алгоритмов
Особенности реализации последовательного алгоритма
Описание локальности данных и вычислений
Возможные способы и особенности реализации параллельного алгоритма
Масштабируемость алгоритма и его реализации
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
- C++, MPI: Parallel Boost Graph Library (функция
strong_components), распределённый алгоритм DCSC сочетается с локальным поиском компонент сильной связности алгоритмом Тарьяна.
Литература
- ↑ 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.
- ↑ 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.
- ↑ 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.