BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-88-1209
       ENTRY:: April 24, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Combinatorial Algorithms for the Generalized Circulation
               Problem
        TYPE:: Technical Report
      AUTHOR:: Goldberg, A. V.
      AUTHOR:: Plotkin, S. A.
      AUTHOR:: Tardos, E.
        DATE:: June 1988
       PAGES:: 38
    ABSTRACT:: We consider a generalization of the maximum flow problem in
               which the amounts of flow entering and leaving an arc are
               linearly related. More precisely, if x(e) units of flow enter
               an arc e, x(e) gamma(e) units arrive at the other end. For
               instance, nodes of the graph can correspond to different
               currencies, with the multipliers being the exchange rates. We
               require conservation of flow at every node except a given
               source node. The goal is to maximize the amount of flow
               excess at the source.

               This problem is a special case of linear programming, and
               therefore can be solved in polynomial time. In this paper we
               present the first polynomial time combinatorial algorithms
               for this problem. The algorithms are simple and intuitive.
       NOTES:: [Adminitrivia V1/Prg/19950424]
         END:: STAN//CS-TR-88-1209