Technical Report CS0103

TR#:CS0103
Class:CS
Title: Two Commodity Flow
Authors: Alon Itai
PDFCS0103.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.
CopyrightThe 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

Computer science department, Technion
admin