Изменения

Поиск максимального паросочетания или минимального вершинного покрытия в двудольном графе совершается за <tex> O(n^3) </tex> операций. При каждом повторении шагов 1-4 в матрице весов появляется новый нуль. Этот нуль соответствует некоторому новому ребру между вершинами из множеств <tex> X \setminus X_c </tex> и <tex> Y \setminus Y_c </tex>. Между вершинами этих множеств ранее не было Всего в графе n^2 ребер, то есть, новое ребро можно добавить в последнее найденное паросочетание, увеличив его размер на 1. Значитзначит, всего будет совершено не более <tex> O(n^2) </tex> итераций внешнего цикла. Поэтому, суммарная асимптотика верхняя оценка времени работы алгоритма данного метода — <tex> O(n^45) </tex>. Более точная оценка довольно сложна и зависит от порядка чисел в матрице весов графа.