Abstract
A zero–one matrix is called perfect if the polytope of the associated set packing problem has integral vertices only. By this definition, all totally unimodular zero–one matrices are perfect. In this paper we give a characterization of perfect zero–one matrices in terms offorbidden submatrices. Perfect zero–one matrices are closely related to perfect graphs and constitute a generalization of balanced matrices as introduced by C. Berge. Furthermore, the results obtained here bear on an unsolved problem in graph theory, the strong perfect graph conjecture, also due to C. Berge.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
E. Balas and M.W. Padberg, “On the set covering problem”,Operations Research 20 (6) (1972).
E. Balas and M.W. Padberg, “On the set covering problem II: An algorithm”, Management Sciences Res. Rept. No. 295 (1972), Carnegie-Mellon University, Pittsburgh, Pa. (presented at the Joint National Meeting of ORSA, TIMS, AIEE, at Atlantic City, November 1972).
C. Berge,Graphes et hypergraphes (Dunod, Paris 1970).
C. Berge, Introduction à la theorie des hypergraphes, Lectures Notes, Université de Montreal, Montreal, Que. (summer 1971).
C. Berge, “Balanced matrices”,Mathematical Programming, 2 (1972) 19–31.
V. Chvátal, “On certain polytopes associated with graphs”, Centre de Recherches Mathematiques, Université de Montreal, Montreal, Que., CRM-238 (October 1972).
D.R. Fulkerson, “Blocking and antiblocking pairs of polyhedra”,Mathematical Programming 1 (1971) 168–194.
D.R. Fulkerson, “On the perfect graph theorem”, in:Mathematical programming, Eds. T.C. Hu and S.M. Robinson (Academic Press, New York, 1973).
F.R. Gantmacher,Matrix theory, Vol II (Chelsea, Bronx, N.Y., 1964).
R. Garfinkel and G. Nemhauser,Integer programming (Wiley, New York, 1972).
B. Grünbaum,Convex polytopes (Wiley, New York, 1966).
A.J. Hoffman, “On combinatorical problems and linear inequalities”, IBM Watson Research Center, Yorktown Heights, N.Y. (paper presented at the 8th International Symposium on Mathematical Programming at Stanford, August 1973).
L. Lovász, “Normal hypergraphs and the Perfect Graph Conjecture”,Discrete Mathematics 2 (1972) 253–268.
L. Lovász, “A characterization of perfect graphs”,Journal of Combinatorial Theory (B) 13 (1972) 95–98.
M.W. Padberg, “On the facial structure of set packing polyhedra”,Mathematical Programming 5 (1973) 199–215.
H. Sachs, “On the Berge conjecture concerning perfect graphs”, in:Combinatorial structures and their applications Eds. R. Guy et al. (Gordon and Breach, New York, 1970).
L. Trotter, “Solution characteristics and algorithms for the vertex packing problem”, Techn. Rept. No. 168, Ph.D. Thesis, Cornell University, Ithaca, N.Y. (January 1973).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Padberg, M.W. Perfect zero–one matrices. Mathematical Programming 6, 180–196 (1974). https://doi.org/10.1007/BF01580235
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01580235