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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
← Предыдущая правкаСледующая правка →
Нет описания правки
Строка 1: Строка 1:
== Свойства и структура алгоритмов ==
== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
=== Общее описание алгоритма ===


'''Алгоритм Тарьяна''' <ref>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.</ref> находит [[Связность в графах|мосты]] в неориентированном графе за время <math>O(m)</math>.
'''Алгоритм Тарьяна''' <ref>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.</ref> находит [[Связность в графах|мосты]] в неориентированном графе за время <math>O(m)</math>.


=== Математическое описание ===
=== Математическое описание алгоритма ===
=== Вычислительное ядро алгоритма ===
=== Вычислительное ядро алгоритма ===
=== Макроструктура алгоритма ===
=== Макроструктура алгоритма ===
=== Описание схемы реализации последовательного алгоритма ===
=== Схема реализации последовательного алгоритма ===
=== Последовательная сложность алгоритма ===
=== Последовательная сложность алгоритма ===


Строка 13: Строка 13:


=== Информационный граф ===
=== Информационный граф ===
=== Описание ресурса параллелизма алгоритма ===
=== Ресурс параллелизма алгоритма ===


Алгоритм Тарьяна может работать с любым остовным деревом, поэтому можно применить эффективно параллелизуемый [[Поиск в ширину (BFS)|поиск в ширину]]. Последующие вычисления также могут быть параллелизованы.
Алгоритм Тарьяна может работать с любым остовным деревом, поэтому можно применить эффективно параллелизуемый [[Поиск в ширину (BFS)|поиск в ширину]]. Последующие вычисления также могут быть параллелизованы.
Строка 19: Строка 19:
Параллельный [[Алгоритм Тарьяна-Вишкина поиска компонент двусвязности|алгоритм Тарьяна-Вишкина]]<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> основан на аналогичных вычислениях и может быть адаптирован для поиска мостов.


=== Описание входных и выходных данных ===
=== Входные и выходные данные алгоритма ===
=== Свойства алгоритма===
=== Свойства алгоритма ===
== Программная реализация алгоритмов ==
 
== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Особенности реализации последовательного алгоритма ===
=== Описание локальности данных и вычислений ===
=== Локальность данных и вычислений ===
=== Возможные способы и особенности реализации параллельного алгоритма ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
=== Существующие реализации алгоритма ===
== Литература ==
== Литература ==
<references />


<references />
[[Категория:Начатые статьи]]

Версия от 11:28, 29 июля 2015

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

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

Алгоритм Тарьяна [1] находит мосты в неориентированном графе за время [math]\displaystyle{ O(m) }[/math].

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

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

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

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

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

Последовательная сложность алгоритма составляет [math]\displaystyle{ O(m) }[/math].

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

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

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

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

Входные и выходные данные алгоритма

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

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

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

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

Локальность реализации алгоритма

Структура обращений в память и качественная оценка локальности
Количественная оценка локальности

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

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

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

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

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

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

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

Литература

  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.
Источник — https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/w/ru/index.php?title=Алгоритм_Тарьяна_поиска_«мостов»_в_графе&oldid=2282