Report Number: CS-TR-88-1209
Institution: Stanford University, Department of Computer Science
Title: Combinatorial Algorithms for the Generalized Circulation
Author: Goldberg, A. V.
Author: Plotkin, S. A.
Author: Tardos, E.
Date: June 1988
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.