Анализ времени работы алгоритма Форда Фулкерсона, который находит максимальный поток в сети

Question

Я знаю, что время работы ford fulkerson в общем случае составляет O(f*(n+m)), где f * - максимальный поток в сети, а n, m - количество вершин и ребер в сети, однако что если все граничные емкости ограничены постоянной C, как это повлияет на время работы?

или это повлияет на время работы?

Answer 1

Предполагая простой граф, данное ограничение в основном означает, что не более c*(n-1) оставить источник. Это означает f* <= c*(n-1), и с тех пор c является постоянным, мы можем сделать вывод, что время выполнения без изменений теперь будет O(n^2+nm),