A PRE - FLOW PUSH ALGORITHM TO GENERALIZED MAXIMUM FLOW PROBLEM

This work presents an algorithm for the generalized maximum flow problem. First, we describe the traditional maximum flow problem. Pre - flow Push algorithms work in a more localized manner than the Ford - Fulkerson method. These algorithms maintain at all sta ges a feasible pre - flow that has a saturated cut. The pre - flow is changed step by step until it does satisfy flow conservation. The resulting flow then has a saturated cut so is a maximum flow. In generalized networks, each arc has a positive multiplier ? ( u , v ) called a gain factor, associated with it, representing the fraction of flow that remains when it is sent along that arc. The generalized maximum flow problem is identical to the traditional maximum flow problem, except that it can also model network with “leak” flow .