Алгоритм Габова определения рёберной связности графа
Свойства и структура алгоритма
Общее описание алгоритма
Алгоритм Габова[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.