Title :Design of algorithms to Generalized Minimum Flow Network Problem
Authors : 1Anto Kinsley , 2B. Uma Maheswari,
In any traditional network, there is an implicit assumption that flow is conserved on every arc. In generalized networks, each arc has a positive multiplier g(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. In this paper, an algorithm is designed for the generalized minimum flow problem that consists of applying a maximum flow algorithm by modifying the network. This algorithm always decreases flow along paths from source vertex to the sink vertex with sufficiently large residual capacity and it runs in O (EV) time.