Abstract
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(
n
2
m) 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.