TY - JOUR

T1 - On fractional multicommodity flows and distance functions

AU - Hurkens, C.A.J.

AU - Schrijver, A.

AU - Tardos, É.

PY - 1989

Y1 - 1989

N2 - We give some results on the existence of fractional and integral solutions to multicommodity flow problems, and on the related problem of decomposing distance functions into cuts. One of the results is: Let G = (V, E) be a planar bipartite graph. Then there exist subsets W1,…, Wt of V so that for each pair υ′, υ″ of vertices on the boundary of G, the distance of υ′ and υ″ in G is equal to the number of j = 1,…, t with |{υ′, υ″} ⋂ Wj| = 1 and so that the cuts δ(Wj) are pairwise disjoint.

AB - We give some results on the existence of fractional and integral solutions to multicommodity flow problems, and on the related problem of decomposing distance functions into cuts. One of the results is: Let G = (V, E) be a planar bipartite graph. Then there exist subsets W1,…, Wt of V so that for each pair υ′, υ″ of vertices on the boundary of G, the distance of υ′ and υ″ in G is equal to the number of j = 1,…, t with |{υ′, υ″} ⋂ Wj| = 1 and so that the cuts δ(Wj) are pairwise disjoint.

U2 - 10.1016/0012-365X(88)90137-9

DO - 10.1016/0012-365X(88)90137-9

M3 - Article

SN - 0012-365X

VL - 73

SP - 99

EP - 109

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-2

ER -