Portal de Periódicos da CAPES

On Odd Cuts and Plane Multicommodity Flows

1981; Wiley; Volume: s3-42; Issue: 1 Linguagem: Inglês

10.1112/plms/s3-42.1.178

1460-244X

Paul Seymour,

Limits and Structures in Graph Theory

Proceedings of the London Mathematical SocietyVolume s3-42, Issue 1 p. 178-192 Articles On Odd Cuts and Plane Multicommodity Flows P. D. Seymour, P. D. Seymour Merton College, Oxford, OX1 4JDSearch for more papers by this author P. D. Seymour, P. D. Seymour Merton College, Oxford, OX1 4JDSearch for more papers by this author First published: January 1981 https://doi.org/10.1112/plms/s3-42.1.178Citations: 105AboutPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Share a linkShare onEmailFacebookTwitterLinkedInRedditWechat Abstract Let T be an even subset of the vertices of a graph G. A T-cut is an edge-cutset of the graph which divides T into two odd sets. We prove that if G is 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. Citing Literature Volumes3-42, Issue1January 1981Pages 178-192 RelatedInformation