Multi-Commodity Network Flows

1963/06/01 by T. C. Hu · 395 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Arc (geometry) #Combinatorics #Commodity #Computer science #Economics #Finance #Flow (mathematics) #Flow network #Geometry #Mathematical optimization #Mathematics #Maximum flow problem #Optimization and Packing Problems #Optimization and Search Problems #Set (abstract data type)

paper · doi:10.1287/opre.11.3.344

published in Operations Research 11(3), 344-360 (Institute for Operations Research and the Management Sciences)

openalex publication_date 1963/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• Improved Lower Bounds on Multiflow-Multicut Gaps
• Optimal Approximations for the Requirement Cut Problem on Sparse Graph Classes
• Multicut Problems in Almost-Planar Graphs: The Dependency of Complexity on the Demand Pattern
• On the Complexity of Timetable and Multicommodity Flow Problems
• Flow-Partitionable Signed Graphs
• The geometry of graphs and some of its algorithmic applications
• Approximating Minimum Feedback Sets and Multicuts in Directed Graphs
• Tools for quantum network design
• AT-Approach to Some Results on Cuts and Metrics
• On the Multiple-Unicast Conjecture: Beyond Cut Metrics
• A Session Interaction Framework for The Multiple-Unicast Conjecture
• The ellipsoid method and its consequences in combinatorial optimization
• Quantum Bridge Analytics II: QUBO-Plus, network optimization and combinatorial chaining for asset exchange. [europepmc]
• Flows of Substances in Networks and Network Channels: Selected Results and Applications. [europepmc]

Related

• A Tight Max-Flow Min-Cut Duality Theorem for Non-Linear Multicommodity Flows
• Finding a Feasible Flow in a Strongly Connected Network
• A New Algorithm for Multicommodity Flow
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Note about network decomposition by maximum flow