Operations Research · 1966 · 74 citations · 1 references
Natural SciencesComputer ScienceComputer NetworksOptimizationSeparation ProcessesCombinatorial OptimizationNetwork Flow AlgorithmsNetwork FlowsNetwork OptimizationCut-flow DualityMaximum FlowMaximum Flow AlgorithmsMulti-commodity FlowMulti-commodity Flow ProblemNetwork Flow Problems
The paper considers the problem of two‑commodity network flows and generalizes a result of Hu on integral flows in networks with integral capacities. The method of proof involves a particular type of separation process. The paper proves a max‑flow min‑cut theorem for two‑commodity networks, presents an algorithm for maximal flows, and provides counterexamples to some generalizations.
The paper considers the problem of two-commodity network flows and generalizes a result of Hu on integral flows in networks with integral capacities. The main result of the paper is a max-flow min-cut theorem for two commodity networks. The method of proof involves a particular type of separation process. This leads to an algorithm for finding the maximal flows. Several counterexamples to certain possible generalizations are given at the end of the paper.
1
T. C. Hu · Operations Research · 1963 · 393 citations