On Odd Cuts and Plane Multicommodity Flows

Research output: Contribution to journalArticle

91 Scopus citations

Abstract

Let Τbe an even subset of the vertices of a graph G.A T-cut is an edge-cutset of the graph which divides Τinto two odd sets. We prove that if Gis bipartite, then the maximum number of disjoint T-cuts is equal to the minimum cardinality of a set of edges which meets every T-cut. (A weaker form of this was proved by Edmonds and Johnson.) We deduce a solution to the real-valued multi-commodity flow problem for a class of planar graphs; and we also solve the integral 2-commodity flow problem for the same class of graphs, by a further analysis of the T-cut problem when T = 4.

Original languageEnglish (US)
Pages (from-to)178-192
Number of pages15
JournalProceedings of the London Mathematical Society
Volumes3-42
Issue number1
DOIs
StatePublished - Jan 1981
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Fingerprint Dive into the research topics of 'On Odd Cuts and Plane Multicommodity Flows'. Together they form a unique fingerprint.

  • Cite this