A Generalization of Two-phase Capacity Scaling Algorithm

In this paper, we generalize the two-phase capacity scaling algorithm in the design of algorithms for the maximum flow problems. The two-phase capacity algorithm uses a factor of value 2 and runs in O(nm log U/n).We consider the general case of scaling factor β. It will be shown that for β≥2 ,the general two-phase capacity scaling algorithm runs in . Furthermore, in the maximum flow problems with U/n ,if we let ,these problems can be solved by using new variant of scaling algorithm in O(nm) time

کلیدواژه ها:

networks flow ، maximum flow problem ، capacity scaling