Matroids and Multicommodity Flows

Research output: Contribution to journalArticle

90 Scopus citations

Abstract

The max-flow min-cut theorem and the two-commodity flow theorem may both be interpreted as equalities between the maximum feasible packing of certain circuits of a graph and the minimum capacity of certain cocircuits, and thus may both be expressed in matroid terms. We study the matroids in which a similar “k-commodity flow theorem” holds. (Thus for k = 1 and 2 it holds for polygon matroids of graphs.) We find for example that such a theorem holds for bond matroids of graphs for all k; and that, for any matroid, if it holds for k = 4, then it holds for all k. We obtain excluded minor characterizations for every k ⩾ 2, and also study the k = 1 case which is still unsolved.

Original languageEnglish (US)
Pages (from-to)257-290
Number of pages34
JournalEuropean Journal of Combinatorics
Volume2
Issue number3
DOIs
StatePublished - Jan 1 1981
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Matroids and Multicommodity Flows'. Together they form a unique fingerprint.

  • Cite this