Алгоритм Габова определения рёберной связности графа

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

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

Алгоритм Габова предназначен для определения рёберной связности графов. Время работы алгоритма $O(k m \ln (n^2/m))$ для ориентированного и $O(m + k^2 n \ln (n/k))$ для неориентированного графа, где $k$ – рёберная связность. Проверка свойства $k$-связности тем же алгоритмом может быть выполнена за время $O(m + n \ln n)$.

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

Время работы алгоритма $O(k m \ln (n^2/m))$ для ориентированного и $O(m + k^2 n \ln (n/k))$ для неориентированного графа, где $k$ – рёберная связность. Проверка свойства $k$-связности тем же алгоритмом может быть выполнена за время $O(m + n \ln n)$.