×

zbMATH — the first resource for mathematics

The matroids with the max-flow min-cut property. (English) Zbl 0375.05022
The max-flow min-cut theorem is possessed by a matroid if and only if the matroid is binary and has no minor which isomorphic to the dual of the Fano matroid.

MSC:
05B35 Combinatorial aspects of matroids and geometric lattices
05C35 Extremal problems in graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Berge, C., ()
[2] Bixby, R.E., \(l\)-matrices and a characterization of binary matroids, Discrete math., 8, 139-145, (1974) · Zbl 0279.05027
[3] Edmonds, J., Edge-disjoint branchings, (), 91-96
[4] Edmonds, J., Submodular functions, matroids, and certain polyhedra, (), 69-87
[5] Edmonds, J.; Fulkerson, D.R., Bottleneck extrema, J. combinatorial theory, 8, 299-306, (1970) · Zbl 0218.05006
[6] Ford, L.R.; Fulkerson, D.R., ()
[7] Fulkerson, D.R., Antiblocking polyhedra, J. combinatorial theory (B), 12, 50-71, (1972) · Zbl 0227.05015
[8] Fulkerson, D.R., Blocking and antiblocking polyhedra, Math. programming, 1, 168-194, (1971) · Zbl 0254.90054
[9] Fulkerson, D.R., Blocking polyhedra, (), 93-112 · Zbl 0217.18505
[10] Fulkerson, D.R., Networks, frames, blocking systems, (), 303-334 · Zbl 0182.53402
[11] Fulkerson, D.R., Packing weighted directed cuts in rooted directed graphs, Math. programming, 6, 1-13, (1974) · Zbl 0283.05104
[12] Gallai, T., Über reguläre kettengruppen, Acta math. acad. sci. hungar., 10, 227-240, (1959) · Zbl 0119.38902
[13] Hu, T.C., Multi-commodity networks flows, Operations res., 11, 344-360, (1963) · Zbl 0123.23704
[14] König, D., Graphen und matrizen, mat. fiz. lapok., 38, 116-119, (1931)
[15] Lehman, A., A solution of the Shannon switching game, J. SIAM, 12, 687-725, (1964) · Zbl 0137.38704
[16] Lehman, A., Matroids and ports, Notices amer. math. soc., 12, 342, (1965)
[17] \scA. Lehman, On the length-width inequality, J. SIAM, to appear. · Zbl 0418.90040
[18] \scL. Lovász, Certain duality principles in integer programming, in Ann. Discrete Math., to appear.
[19] Lovász, L., Minimax theorems for hypergraphs, (), 111-126, No. 411
[20] Lovász, L., Normal hypergraphs and the perfect graph conjecture, Discrete math., 2, 253-267, (1972) · Zbl 0239.05111
[21] \scC. Lucchesi and D. H. Younger, A minimax theorem for directed graphs, Proc. London Math. Soc., to appear. · Zbl 0392.05029
[22] Menger, K., Zur allgemeine kurventheorie, Fund. math., 10, 96-115, (1927) · JFM 53.0561.01
[23] Minty, G.J., On the axiomatic foundations of the theories of directed linear graphs, electrical networks and network programming, J. math. mech., 15, 485-520, (1966) · Zbl 0141.21601
[24] Seymour, P.D., A forbidden minor characterization of matroid ports, Quart. J. math. Oxford, 27, 2, 407-413, (1976) · Zbl 0366.05022
[25] Seymour, P.D., A note on the production of matroid minors, J. combinatorial theory (B), 22, 289-295, (1977) · Zbl 0385.05021
[26] \scP. D. Seymour, Matroid representation over GF(3), J. Combinatorial Theory (B), to appear. · Zbl 0443.05029
[27] \scP. D. Seymour, On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte, Proc. London Math. Soc., to appear. · Zbl 0411.05037
[28] Seymour, P.D., The forbidden minors of binary clutters, J. London math. soc., 12, 2, 356-360, (1976) · Zbl 0351.05023
[29] Tutte, W.T., A homotopy theorem for matroids, II, Trans. amer. math. soc., 88, 161-174, (1958) · Zbl 0081.17301
[30] Tutte, W.T., Introduction to the theory of matroids, (1966), Rand Corporation Report R-448-PR · Zbl 0149.21501
[31] Tutte, W.T., Lectures on matroids, J. res. nat. bur. standards sect. B, 69, 1-47, (1965) · Zbl 0151.33801
[32] Welsh, D.J.A., ()
[33] Woodall, D.R., Property B and the four-colour problem, (), 322-340
[34] Hu, T.C., Two-commodity cut-packing problem, Math. programming, 4, 108-109, (1973) · Zbl 0255.90067
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.