Generalized maximum flow algorithms
Éva Tardos, Kevin D. Wayne · 1999
We present several new efficient algorithms for the generalized maximum flow problem. In the traditional maximum flow problem, there is a capacitated network and the goal is to send as much of a single commodity as possible between two distinguished nodes, without exceeding the arc capacity limits. The problem has hundreds of applications including: shipping freight in a transportation network and pumping fluid through a hydraulic network. In traditional networks, there is an implicit assumption that flow is conserved on every arc. Many practical applications violate this conservation assumption. Freight may be damaged or spoil in transit; fluid may or evaporate. In generalized networks, each arc has a positive multiplier 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 networks which leak flow.