Алгоритм Габова определения рёберной связности графа: различия между версиями
| [досмотренная версия] | [досмотренная версия] |
ASA (обсуждение | вклад) Нет описания правки |
ASA (обсуждение | вклад) Нет описания правки |
||
| Строка 21: | Строка 21: | ||
== Программная реализация алгоритма == | == Программная реализация алгоритма == | ||
=== Особенности реализации последовательного алгоритма === | === Особенности реализации последовательного алгоритма === | ||
=== Возможные способы и особенности параллельной реализации алгоритма === | === Возможные способы и особенности параллельной реализации алгоритма === | ||
=== | === Результаты прогонов === | ||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
== Литература == | == Литература == | ||
<references /> | <references /> | ||
Текущая версия от 14:55, 6 июля 2022
Свойства и структура алгоритма
Общее описание алгоритма
Алгоритм Габова[1] предназначен для определения рёберной связности графов. Время работы алгоритма [math]\displaystyle{ O(k m \ln (n^2/m)) }[/math] для ориентированного и [math]\displaystyle{ O(m + k^2 n \ln (n/k)) }[/math] для неориентированного графа, где [math]\displaystyle{ k }[/math] – рёберная связность. Проверка свойства [math]\displaystyle{ k }[/math]-связности тем же алгоритмом может быть выполнена за время [math]\displaystyle{ O(m + n \ln n) }[/math].
Математическое описание алгоритма
Вычислительное ядро алгоритма
Макроструктура алгоритма
Схема реализации последовательного алгоритма
Последовательная сложность алгоритма
Время работы алгоритма [math]\displaystyle{ O(k m \ln (n^2/m)) }[/math] для ориентированного и [math]\displaystyle{ O(m + k^2 n \ln (n/k)) }[/math] для неориентированного графа, где [math]\displaystyle{ k }[/math] – рёберная связность. Проверка свойства [math]\displaystyle{ k }[/math]-связности тем же алгоритмом может быть выполнена за время [math]\displaystyle{ O(m + n \ln n) }[/math].
Информационный граф
Ресурс параллелизма алгоритма
Входные и выходные данные алгоритма
Свойства алгоритма
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Возможные способы и особенности параллельной реализации алгоритма
Результаты прогонов
Выводы для классов архитектур
Литература
- ↑ Gabow, H N. “A Matroid Approach to Finding Edge Connectivity and Packing Arborescences.” Journal of Computer and System Sciences 50, no. 2 (April 1995): 259–73. doi:10.1006/jcss.1995.1022.