LCS Publication Details
Publication Title: COMBINATORIAL ALGORITHMS FOR THE GENERALIZED CIRCULATION PROBLEM
Publication Author: Goldberg, Andrew V.
Additional Authors: Plotkin, Serge A. and Tardos, Eva
LCS Document Number: MIT-LCS-TM-358
Publication Date: 5-1-1988
LCS Group: No Group Specified
Additional URL: No URL Given
Abstract:
We consider a generalization of the maximum flow problem in which the amounts of flow entering and leaving an are are linearly related. More precisely, if x(e) units of flow enter an are e, x(e).(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 expect a given source node. The goal is to maximize the amount of flow excess at the source.
To obtain this publication:

    To purchase a printed copy of this publication please contact MIT Document Services.