×

zbMATH — the first resource for mathematics

Edmonds polytopes and a hierarchy of combinatorial problems. (English) Zbl 0253.05131

MSC:
05C65 Hypergraphs
90C10 Integer programming
90C27 Combinatorial optimization
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
PDF BibTeX Cite
Full Text: DOI
References:
[1] Balas, E., A note on the branch-and-bound principle, Operations res., 16, 443-445, (1968) · Zbl 0186.24901
[2] Berge, C., Graphes et hypergraphs, (1970), Dunod Paris · Zbl 0213.25702
[3] Chvátal, V., Hypergraphs and Ramseyian theorems, Proc. am. math. soc., 27, 434-440, (1971) · Zbl 0255.05108
[4] Chvátal, V., Remarks on a problem of Moser, Canad. math. bull., 15, 19-21, (1972) · Zbl 0232.05002
[5] V. Chvátal, Edmonds polytopes and weakly Hamiltonian graphs, Math. Programming, to appear. · Zbl 0267.05118
[6] V. Chvátal, On certain polytopes associated with graphs, submitted to J. Combin. Theory. · Zbl 0226.05106
[7] Cook, S.A., The complexity of theorem-proving procedures, Conference record of third ACM symposium on theory of computing, 151-158, (1970)
[8] Edmonds, J., Minimum partition of a matroid into independent subsets, J. res. nat. bur. standards sect. B, 69, 67-72, (1965) · Zbl 0192.09101
[9] Edmonds, J., Maximum matching and a polyhedron with 0, 1-vertices, J. res. nat. bur. standards sect. B, 69, 125-130, (1965) · Zbl 0141.21802
[10] Edmonds, J., Paths, tree and flowers, Canad. J. math., 17, 449-467, (1965) · Zbl 0132.20903
[11] Edmonds, J.; Johnson, E.L., Matching: A well-solved class of integer linear programs, () · Zbl 1024.90505
[12] Edmonds, J.; Karp, R.M., Theoretical improvements in algorithmic efficiency for network flow problems, () · Zbl 0248.90056
[13] Erdös, P., Some remarks on the theory of graphs, Bull. amer. math. soc., 53, 292-294, (1947) · Zbl 0032.19203
[14] Fulkerson, D.R., Anti-blocking polyhedra, J. combin. theory, 12, 50-71, (1972) · Zbl 0227.05015
[15] Gallai, T., On directed paths and circuits, () · Zbl 0159.54403
[16] Gomory, R.E., An algorithm for integer solutions to linear programs, (), (1958), also in: · Zbl 0132.13702
[17] Hall, M., Combinatorial theory, (1967), Blaisdell Waltham, Mass · Zbl 0196.02401
[18] Hoffman, A.J.; Kruskal, J.B., Integral boundary points of convex polyhedra, () · Zbl 0072.37803
[19] Hopcroft, J.; Karp, R.M., A \(n\^{}\{52\}\) algorithm for maximum matchings in bipartite graphs, Twelfth annual symposium on switching and automata theory, 122-125, (1971)
[20] Hu, T.C., Integer programming and network flows, (1969), Addison-Wesley Reading, Mass · Zbl 0197.45701
[21] Karp, R.M., Reducibility among combinatorial problems, () · Zbl 0366.68041
[22] Lovász, L., Normal hypergraphs and the perfect graph conjecture, Discrete math., 2, 253-268, (1972) · Zbl 0239.05111
[23] Lovász, L., A characterization of perfect graphs, J. combin. theory, 13, 95-98, (1972) · Zbl 0241.05107
[24] Moser, L., Problem P. 170, Canad. math. bull., 13, 268, (1970)
[25] Trotter, L.E., Solution characteristics and algorithms for the vertex-packing problem, ()
[26] Tutte, W.T., The factorization of linear graphs, J. London math. soc., 22, 107-111, (1947) · Zbl 0029.23301
[27] Veinott, A.F.; Dantzig, G.B., Integer extreme points, SIAM review, 10, 371-372, (1968) · Zbl 0162.33401
[28] Wolf, T., The electric kool-acid acid test, (1969), Bantam Books
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.