Изменения

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