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

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

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

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

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

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