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