Алгоритм Тарьяна поиска компонент двусвязности: различия между версиями

[непроверенная версия]

Версия 02:12, 11 июня 2015

Содержание

1 Свойства и структура алгоритмов
2 Программная реализация алгоритмов
3 Литература

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

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

Алгоритм Тарьяна^[1] находит компоненты двусвязности и шарниры неориентированного графа в процессе поиска в глубину за время [math]O(m)[/math].

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

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

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

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

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

Последовательная сложность алгоритма Тарьяна составляет [math]O(m)[/math], так как в процессе поиска в ширину выполняется ограниченное количество операций для каждой вершины и каждого ребра.

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

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

Возможности параллелизации алгоритма Тарьяна сильно ограничены, поскольку он основан на поиске в глубину. Параллельный алгоритмом Тарьяна-Вишкина^[2] основан на тех же свойствах графа и может использовать любое остовное дерево.

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

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

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

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

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

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

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

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

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

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

Boost Graph Library (функция biconnected_components).

3 Литература

↑ Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.
↑ Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.

[1] Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.

[2] Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.

[1]

[2]

@@ Строка 2: / Строка 2: @@
 === Общее описание алгоритма ===
-'''Алгоритм Тарьяна'''<ref>Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.</ref> находит [[Связность в графах|компоненты двусвязности]] неориентированного графа в процессе [[Поиск в глубину (DFS)|поиска в глубину]]) за время <math>O(m)</math>.
+'''Алгоритм Тарьяна'''<ref>Tarjan, Robert. “Depth-First Search and Linear Graph Algorithms.” SIAM Journal on Computing 1, no. 2 (1972): 146–60.</ref> находит [[Связность в графах|компоненты двусвязности]] и шарниры неориентированного графа в процессе [[Поиск в глубину (DFS)|поиска в глубину]] за время <math>O(m)</math>.
 === Математическое описание ===