DOIAbstract
Suppose that G is an undirected graph whose edges have nonnegative integral capacities, that s1,...,sk are k distinguished vertices in G, and that dij, 1≤i<j≤k, are nonnegative integral demands. We consider the problem of existence of an admissible multicommodity flow F= fij: 1 ≤i<j≤k in which each Fij is a flow of value dij between si, and sj. It is known that if k≥5, then satisfying the obvious requirements of Ford-Fulkerson's type (concerning cuts of G) does not guarantee, in general, that such a multicommodity flow exists. We give a combinatorial criterion of solvability of this problem for k = 5 and prove that if k = 5 and the problem has a solution, then it has also a half-integral solution. This generalizes a number of known results ...
Add to ORKG