Алгоритм Тарьяна-Вишкина поиска компонент двусвязности

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

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

Параллельный алгоритм Тарьяна-Вишкина находит компоненты двухсвязности неориентированного графа за время [math]\displaystyle{ O(\ln n) }[/math] на [math]\displaystyle{ O(m + n) }[/math] процессорах. Алгоритм может быть адаптирован для поиска мостов. Эффективность алгоритма Тарьяна-Вишкина подтверждена в последнее время как на системах архитектуры SMP, так и при вычислениях на GPU.

Математическое описание алгоритма

1. Для каждой компоненты связности графа найти какое-либо остовное дерево [math]\displaystyle{ T }[/math].

2. Перенумеровать вершины [math]\displaystyle{ T }[/math] в порядке обратного обхода.

3. В порядке возрастания номера вершины выполнить следующие действия:

a. [math]\displaystyle{ D(v) := 1+ \sum_{v \rightarrow w}D(w) }[/math]

b. [math]\displaystyle{ L(v) := \min { \{N(v) - D(v)+1 \} \cup \{ L(w) | v \rightarrow w \} \cup \{ N(w) | v \cdots w \} } }[/math]

c. [math]\displaystyle{ H(v) := \max { \{ N(v) \} \cup \{ H(w) | v \rightarrow w \} \cup \{ N(w) | v \cdots w \} } }[/math]

d. Пометить ребро [math]\displaystyle{ v \rightarrow w }[/math] мостом, если [math]\displaystyle{ H(w)\lt =N(w) }[/math] и [math]\displaystyle{ L(w)\gt N(w)-D(w) }[/math].

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

На первом шаге работы алгоритма строится остовный лес графа с использованием модифицированного алгоритма Шилоаха-Вишкина.

Для этого для каждой вершины [math]\displaystyle{ v }[/math] определяется указатель на родительскую вершину [math]\displaystyle{ P(v) }[/math]; на шаге инициализации [math]\displaystyle{ P(v):=v }[/math]. Далее остовный лес строится чередованием двух параллельных операций:

• Удвоение указателей: [math]\displaystyle{ P(v):=P(P(v)) }[/math] ;

• Соединение: [math]\displaystyle{ P(P(v)):=P(w) }[/math], где [math]\displaystyle{ v }[/math] – вершина [math]\displaystyle{ P }[/math]-дерева ( [math]\displaystyle{ P(v)=v }[/math]на текущем шаге), [math]\displaystyle{ w }[/math]– некоторая вершина, для которой существует ребро [math]\displaystyle{ (v,w)\in E }[/math]. Ребро помечается, как принадлежащее остовному лесу .

Далее производятся следующие шаги:

• перенумерация вершин в обратном порядке обхода (post-order);

• вычисление количества потомков [math]\displaystyle{ D(v) }[/math] для каждой вершины;

• вычисление значений [math]\displaystyle{ L(v) }[/math] и [math]\displaystyle{ H(v) }[/math] для каждой вершины;

• пометка рёбер [math]\displaystyle{ v \rightarrow w }[/math] мостами, если [math]\displaystyle{ H(w)\lt =N(w) }[/math] и [math]\displaystyle{ L(w)\gt N(w)-D(w) }[/math].

Основной идеей для обеспечения завершения работы алгоритма за [math]\displaystyle{ O(ln n) }[/math] шагов является систематическое использование операции удвоения указателей.

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

Последовательный вариант алгоритма аналогичен алгоритму Тарьяна и имеет линейную сложность [math]\displaystyle{ O(m + n) }[/math].

Ресурс параллелизма алгоритма

Алгоритм изначально параллельный, время работы [math]\displaystyle{ O(\ln n) }[/math] на [math]\displaystyle{ O(m + n) }[/math] процессорах.

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

1. Компонента сильной связности – подграф, любые две вершины которого принадлежат какому-либо циклу, и содержащий все такие циклы для своих вершин.

2. Компонента сильной связности является объединением всех циклом, проходящих через её вершины.