The matroids with the max-flow min-cut property

P. D. Seymour

doi:10.1016/0095-8956(77)90031-4

The matroids with the max-flow min-cut property

P. D. Seymour

Research output: Contribution to journal › Article › peer-review

161 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 language	English (US)
Pages (from-to)	189-222
Number of pages	34
Journal	Journal of Combinatorial Theory, Series B
Volume	23
Issue number	2-3
DOIs	https://doi.org/10.1016/0095-8956(77)90031-4
State	Published - 1977
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/0095-8956(77)90031-4

Cite this

@article{f76ced31d84c4120823e0c7f5824fcbd,

title = "The matroids with the max-flow min-cut property",

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.",

author = "Seymour, {P. D.}",

year = "1977",

doi = "10.1016/0095-8956(77)90031-4",

language = "English (US)",

volume = "23",

pages = "189--222",

journal = "Journal of Combinatorial Theory, Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "2-3",

}

TY - JOUR

T1 - The matroids with the max-flow min-cut property

AU - Seymour, P. D.

PY - 1977

Y1 - 1977

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0000327178&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0000327178&partnerID=8YFLogxK

U2 - 10.1016/0095-8956(77)90031-4

DO - 10.1016/0095-8956(77)90031-4

M3 - Article

AN - SCOPUS:0000327178

SN - 0095-8956

VL - 23

SP - 189

EP - 222

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

IS - 2-3

ER -

The matroids with the max-flow min-cut property

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this