Premium
Synthesis of directed multicommodity flow networks
Author(s) -
Itai A.,
Pradhan D. K.
Publication year - 1984
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230140203
Subject(s) - multi commodity flow problem , polyhedron , flow network , flow (mathematics) , mathematics , mathematical optimization , constant (computer programming) , maximum flow problem , computer science , combinatorics , geometry , programming language
A necessary condition for synthesis of multicommodity flow networks is derived. The feasible flow region of a multicommodity flow network is shown to be an antiblocking polyhedron with rational slopes. 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 pseudolinear; in the worst case the network found by the algorithm is optimal to within a constant factor.