×

zbMATH — the first resource for mathematics

Vertex packings: structural properties and algorithms. (English) Zbl 0314.90059

MSC:
90C10 Integer programming
52C17 Packing and covering in \(n\) dimensions (aspects of discrete geometry)
90C35 Programming involving graphs or networks
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] E. Balas and H. Samuelsson, ”Finding a minimum node cover in an arbitrary graph”, Management Sciences Research Rept. No. 325, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, Pa. (November 1973).
[2] M.L. Balinski, ”On maximum matching, minimum covering and their connections”, in: H.W. Kuhn, ed.,Proceedings of the Princeton symposium on mathematical programming, (Princeton University Press, Princeton, N.J., 1970) pp. 303–312. · Zbl 0228.05122
[3] C. Berge,The theory of graphs and its applications (Methuen, London, 1962). · Zbl 0097.38903
[4] V. Chvátal, ”On certain polytopes associated with graphs”, Centre de Recherches Mathématiques-238, Université de Montréal (October 1972). · Zbl 0277.05139
[5] V. Chvátal, ”Edmonds polytopes and a hierarchy of combinatorial problems”,Discrete Mathematics 5 (1973) 305–337. · Zbl 0253.05131 · doi:10.1016/0012-365X(73)90167-2
[6] J. Edmonds, ”Covers and packings in a family of sets”,Bulletin of the American Mathematical Society 68 (1962) 494–499. · Zbl 0106.24201 · doi:10.1090/S0002-9904-1962-10791-5
[7] J. Edmonds, ”Paths, trees, and flowers”,Canadian Journal of Mathematics 17 (1965) 449–467. · Zbl 0132.20903 · doi:10.4153/CJM-1965-045-4
[8] L.R. Ford, Jr. and D.R. Fulkerson,Flows in networks (Princeton University Press, Princeton, N.J., 1962). · Zbl 0106.34802
[9] D.R. Fulkerson, ”Anti-blocking polyhedra”,Journal of Combinatorial Theory 12 (1972) 50–71. · Zbl 0227.05015 · doi:10.1016/0095-8956(72)90032-9
[10] F. Gavril, ”Algorithms for minimum coloring, maximum clique, minimum covering by cliques and maximum independent set of a chordal graph”,SIAM Journal of Computing 1 (1972) 180–187. · Zbl 0227.05116 · doi:10.1137/0201013
[11] A.M. Geoffrion, ”An improved implicit enumeration approach for integer programming”,Operations Research 17 (1969) 437–454. · Zbl 0174.20801 · doi:10.1287/opre.17.3.437
[12] R.M. Karp, ”Reducibility among combinatorial problems”, in: R.E. Miller, J.W. Thatcher and J.D. Bohlinger, eds.,Complexity of computer computations (Plenum Press, New York, 1972) pp. 85–103.
[13] C.E. Lemke, H.M. Salkin and K. Spielberg, ”Set covering by single branch enumeration with linear programming subproblems”,Operations Research 19 (1971) 998–1022. · Zbl 0232.90033 · doi:10.1287/opre.19.4.998
[14] G.L. Nemhauser and L.E. Trotter, Jr., ”Properties of vertex packing and independence system polyhedra”,Mathematical Programming 6 (1974) 48–61. · Zbl 0281.90072 · doi:10.1007/BF01580222
[15] M. Padberg, ”On the facial structure of set packing polyhedra”,Mathematical programming 5 (1973) 199–216. · Zbl 0272.90041 · doi:10.1007/BF01580121
[16] R. Tarjan, ”Finding a maximum clique”, Tech. Rept. 72-123, Dept. of Computer Science, Cornell University, Ithaca, N.Y. (March 1972).
[17] L.E. Trotter, Jr., ”Solution characteristics and algorithms for the vertex packing problem”, Tech. Rept. No. 168, Dept. of Operations Research, Cornell University, Ithaca, N.Y. (January 1973).
[18] L.E. Trotter, Jr., ”A class of facet producing graphs for vertex packing polyhedra”, Research Rept. No. 78, Dept. of Administrative Sciences, Yale University, New Haven, Conn. (February 1974).
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.