LAYERING ALGORITHM FOR GENERALIZED MAXIMUM FLOW NETWORK PROBLEM

Abstract

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. This work presents how to find the capacity of each tube in the network, time of flow in the path of the network and also an algorithm for the generalized maximum flow problem. First, we describe the traditional maximum flow algorithm of layered networks, it is fast and extremely simple and elegant in its conception  and so it represents a good choice for those who may wish to program one of if these algorithms for themselves.