Perfect 0, ± 1 matrices were introduced recently in (Conforti, Cornuejols and De Francesco, 1993) as a generalization of the well-studied class of perfect 0, 1 matrices. In this paper we provide a characterization of perfect 0, ± 1 matrices in terms of an associated perfect graph which one can build in O(n2m) time, where m × n is the size of the matrix. We also obtain an algorithm of the same time complexity, for testing the irreducibility of the corresponding generalized set packing polytope.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics