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

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

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


algorithm graph-algorithm ford-fulkerson
person user3510049    schedule 08.04.2014    source источник

Ответы (1)


arrow_upward
1
arrow_downward

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

person amit    schedule 08.04.2014