On perfect 0, ± 1 matrices Original Research Article

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.