Technical Report CS0181

Title: Synthesis Of Multi-commodity Flow Problems
Authors: A. Itai and D.K. Pradhan
Abstract: A necessary condition for synthesis of multi-commodity flow networks is derived. The feasible flow region of a multi-commodity flow network is shown to be an integer anti-blocking polyhedron. Also, it is established that this condition is sufficient for two-commodity flow networks. A synthesis algorithm for two-commodity flow networks is proposed. The size of the resulting networks is studied and for some regions it is shown to be pseuso-linear, and the network found by the algorithm is essentially optimal.
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 (, 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 1980
To the main CS technical reports page

Computer science department, Technion