Изменения

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