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

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

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

Алгоритм Габова предназначен для определения рёберной связности графов. Время работы алгоритма [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].