COMBINATORIAL ALGORITHMS FOR THE GENERALIZED CIRCULATION PROBLEM

• 成果类型: Article
• 署名作者: GOLDBERG, AV; PLOTKIN, SA; TARDOS, E
• 署名单位: Stanford University; Cornell University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.16.2.351
• 发表日期: 1991
• 页码: 351-381
• 关键词: network; trees; gains; FLOW

摘要

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.