Multi-Commodity Network Flows 论文

详细信息

发表期刊/会议

Operations Research

发表日期

1963-06-01

发表年份

1963

摘要

A network is a set of nodes N ı connected by arcs with nonnegative arc capacities b ıj which indicates the maximum amount of flow that can pass through the arc from N ı to N j . Given all b ıj , there is a maximum flow from N ı to N j using all arcs. Under the assumption that b ıj = b jı , the present paper generalizes the max-flow min-cut theorem of Ford and Fulkerson to the problem of finding the maximum simultaneous flows of two commodities and gives an algorithm similar to the labelling method for constructing the two flows.