Two-Commodity Flow
- 1 October 1978
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 25 (4), 596-611
- https://doi.org/10.1145/322092.322100
Abstract
An algorithm is given to fmd maxtmum two-commodity flow m an undirected graph The algorithm is an improvement on Hu's two-commodity flow algorithm using the methods of Dmlc's single-commodity flow algorithm Karzanov's Improvement of Dmlc's algorithm can be applied to yield an O(I V ) 3) algorithm. It is shown that finding maximum two-commodity flow m a dwected graph is much more dffficuh, in fact it Is as difficult as hnear programming FmaUy, the problem of finding feasible flow m an undirected graph with lower and upper bounds on the edges is shown to be NP-complete even for a single commodityKeywords
This publication has 5 references indexed in Scilit:
- On the Complexity of Timetable and Multicommodity Flow ProblemsSIAM Journal on Computing, 1976
- Network Flow and Testing Graph ConnectivitySIAM Journal on Computing, 1975
- On the Structure of Polynomial Time ReducibilityJournal of the ACM, 1975
- Theoretical Improvements in Algorithmic Efficiency for Network Flow ProblemsJournal of the ACM, 1972
- Theoretical Efficiency of the Edmonds-Karp Algorithm for Computing Maximal FlowsJournal of the ACM, 1972