On fractional multicommodity flows and distance functions

C.A.J. Hurkens, A. Schrijver, É. Tardos

Research output: Contribution to journalArticleAcademicpeer-review

4 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)99-109
JournalDiscrete Mathematics
Volume73
Issue number1-2
DOIs
Publication statusPublished - 1989

Fingerprint Dive into the research topics of 'On fractional multicommodity flows and distance functions'. Together they form a unique fingerprint.

Cite this