The matroids with the max-flow min-cut property

Research output: Contribution to journalArticle

139 Scopus citations

Abstract

The max-flow min-cut theorem of Ford and Fulkerson (for undirected networks) may be regarded as a statement about the circuits and cocircuits using some fixed element of the cycle matroid of a graph. We show that, in general, a matroid has this property (in the integer form) if and only if it is binary and has no minor isomorphic to the dual of the Fano matroid.

Original languageEnglish (US)
Pages (from-to)189-222
Number of pages34
JournalJournal of Combinatorial Theory, Series B
Volume23
Issue number2-3
DOIs
StatePublished - Jan 1 1977
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'The matroids with the max-flow min-cut property'. Together they form a unique fingerprint.

  • Cite this