×

zbMATH — the first resource for mathematics

On shortest \(T\)-joins and packing \(T\)-cuts. (English) Zbl 0810.05056
Summary: We give a class of graphs with the property that for each even set \(T\) of nodes in \(G\) the minimum length of a \(T\)-join is equal to the maximum number of pairwise edge disjoint \(T\)-cuts. Our class contains the bipartite and the series-parallel graphs for which this property was derived earlier by Seymour.

MSC:
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C35 Extremal problems in graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Edmonds, J, The Chinese postman problem, Oper. res., 13, Suppl. 1, 373, (1965)
[2] Edmonds, J; Johnson, E, Matching: A well solved class of integer programs, (), 89-92
[3] Edmonds, J; Johnson, E.L, Matching, Euler tours and the Chinese postman problem, Math. programming, 5, 88-124, (1973) · Zbl 0281.90073
[4] Frank, A; Sebő, A; Tardos, É, Covering directed and odd cuts, Math. programming study, 22, 99-112, (1984) · Zbl 0556.90060
[5] Gerards, A.M.H; Schrijver, A, Matrices with the edmonds-Johnson property, Combinatoria, 6, 365-379, (1986) · Zbl 0641.05039
[6] Korach, E, Packing of t-cuts and other aspects of dual integrality, ()
[7] Korach, E; Penn, M, (), Technical Report No. 360
[8] Lovász, L, 2-matchings and 2-covers of hypergraphs, Acta math. acad. sci. hungar., 26, 433-444, (1975) · Zbl 0339.05123
[9] Menger, K, Zur allgemeinen kurventheorie, Fund. math., 10, 96-115, (1927) · JFM 53.0561.01
[10] Guan, Mei Gu, Graphic programming using odd or even points, Chinese J. math., 1, 273-277, (1962) · Zbl 0143.41904
[11] Middendorf, M; Pfeiffer, F, On the complexity of the disjoint path problem, (), 171-178
[12] Sebő, A, Finding the t-join structure of graphs, Math. programming, 36, 123-134, (1986) · Zbl 0626.90090
[13] Sebő, A, A quick proof of Seymour’s theorem on t-joins, Discrete math., 64, 101-103, (1987) · Zbl 0618.05040
[14] Sebő, A, The schrijver system of odd-join polyhedra, Combinatorica, 8, 103-116, (1988) · Zbl 0642.90096
[15] Sebő, A, Undirected distances and the structure of odd-joins, J. combin. theory ser. B, 49, 10-39, (1990) · Zbl 0638.05032
[16] Sebő, A, The cographic multiflow problem: an epilogue, (), 203-234 · Zbl 0733.05028
[17] Seymour, P.D, Matroids with the MAX-flow MIN-cut property, J. combin. theory ser. B, 23, 189-222, (1977) · Zbl 0375.05022
[18] Seymour, P.D, On odd cuts and plane multi-commodity flows, (), 178-192 · Zbl 0447.90026
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.