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

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

Версия 12:30, 7 июля 2015

Содержание

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

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

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

Алгоритм Тарьяна ^[1] находит мосты в неориентированном графе за время $O(m)$ .

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

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

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

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

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

Последовательная сложность алгоритма составляет $O(m)$ .

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

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

Алгоритм Тарьяна может работать с любым остовным деревом, поэтому можно применить эффективно параллелизуемый поиск в ширину. Последующие вычисления также могут быть параллелизованы.

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

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

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

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

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

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

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

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

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

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

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

3 Литература

↑ Tarjan, R Endre. “A Note on Finding the Bridges of a Graph.” Information Processing Letters 2, no. 6 (April 1974): 160–61. doi:10.1016/0020-0190(74)90003-9.
↑ Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.

[1] Tarjan, R Endre. “A Note on Finding the Bridges of a Graph.” Information Processing Letters 2, no. 6 (April 1974): 160–61. doi:10.1016/0020-0190(74)90003-9.

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

[1]

[2]

@@ Строка 17: / Строка 17: @@
 Алгоритм Тарьяна может работать с любым остовным деревом, поэтому можно применить эффективно параллелизуемый [[Поиск в ширину (BFS)|поиск в ширину]]. Последующие вычисления также могут быть параллелизованы.
-Параллельный [[Алгоритм Тарьяна поиска компонент двусвязности|алгоритм Тарьяна-Вишкина]]<ref>Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.</ref> основан на аналогичных вычислениях и может быть адаптирован для поиска мостов.
+Параллельный [[Алгоритм Тарьяна-Вишкина поиска компонент двусвязности|алгоритм Тарьяна-Вишкина]]<ref>Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.</ref> основан на аналогичных вычислениях и может быть адаптирован для поиска мостов.
 === Описание входных и выходных данных ===