TY - JOUR
T1 - On perfect 0, ± 1 matrices 1, 2
AU - Boros, Endre
AU - Čepek, Ondřej
N1 - Funding Information:
* Corresponding author. E-mail: boros@rutcor.rutgers.edu. ’ This research was partially supported by the OfIke of Naval Research (grants N0001492F1375 ancl N0001492F4083) and by the Air Force Office of Scientific Research (grant F49620-93-l-0041). * Revised version of RUTCOR Research Report 20-95, May 1995.
PY - 1997/3/15
Y1 - 1997/3/15
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=17744411560&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=17744411560&partnerID=8YFLogxK
U2 - 10.1016/S0012-365X(96)00163-X
DO - 10.1016/S0012-365X(96)00163-X
M3 - Article
AN - SCOPUS:17744411560
SN - 0012-365X
VL - 165-166
SP - 81
EP - 100
JO - Discrete Mathematics
JF - Discrete Mathematics
ER -