| TR#: | CS0103 |
| Class: | CS |
| Title: | Two Commodity Flow |
| Authors: | Alon Itai |
| CS0103.pdf | |
| Abstract: | An algorithm is given to find maximum two commodity flow in an undirected graph. The algorithm is an improvement of T.C. Hu's two commodity flow algorithm using the methods of Dinic's single commodjty flow algorithm. Karzanov's improvement of Dinic's algorithm can be applied to yield an O(|v|^3) algorithm. It is shown that finding maximum two commodity flow in a directed graph is much mere difficult and in fact is as hard as linear programming. Finally, the problem of finding feasible flow in an undirected graph with lower and upper bounds on the edges is shown to be NP-complete for a single commodity. |
| Copyright | The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information |
Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1977/CS/CS0103), rather than to the URL of the PDF files directly. The latter URLs may change without notice.
To the list of the CS technical reports of 1977
To the main CS technical reports page