1

Тема: min-cost-max-flow методом увеличивающих путей

По аналогии с анализом алгоритма Эдмондса-Карпа, мы получаем такую оценку: O (N M) * T (N, M), где T (N, M) - время, необходимое для нахождения кратчайшего пути в графе с N вершинами и M рёбрами.

Нельзя ли поподробнее, как получается эта оценка? В анализе Эдмондса-Карпа существенно, что мы делаем bfs, т.е., что все "стоимости" единичные. Да и в книжке "Ahuja, Magnanti, Orlin. Network flows" приводится оценка O(N U T(N, M)), где U - максимальная пропускная способность.

2

Re: min-cost-max-flow методом увеличивающих путей

Неправильная оценка, наверное, да.
Ох, много работы предстоит по пересмотру старых статей, написанных в незапамятные времена... smile