Алгоритм Тарьяна поиска компонент двусвязности
Свойства и структура алгоритмов
Общее описание алгоритма
Алгоритм Тарьяна[1] находит компоненты двусвязности неориентированного графа в процессе поиска в глубину) за время [math]\displaystyle{ O(m) }[/math].
Математическое описание
Вычислительное ядро алгоритма
Макроструктура алгоритма
Описание схемы реализации последовательного алгоритма
Последовательная сложность алгоритма
Последовательная сложность алгоритма Тарьяна составляет [math]\displaystyle{ O(m) }[/math], так как в процессе поиска в ширину выполняется ограниченное количество операций для каждой вершины и каждого ребра.
Информационный граф
Описание ресурса параллелизма алгоритма
Возможности параллелизации алгоритма Тарьяна сильно ограничены, поскольку он основан на поиске в глубину. Параллельный алгоритмом Тарьяна-Вишкина[2] основан на тех же свойствах графа и может использовать любое остовное дерево.
Описание входных и выходных данных
Свойства алгоритма
Программная реализация алгоритмов
Особенности реализации последовательного алгоритма
Описание локальности данных и вычислений
Возможные способы и особенности реализации параллельного алгоритма
Масштабируемость алгоритма и его реализации
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
- Boost Graph Library (функция
biconnected_components).