On perfect 0, ± 1 matrices 1, 2

Endre Boros, Ondřej Čepek

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

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(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.

Original languageEnglish (US)
Pages (from-to)81-100
Number of pages20
JournalDiscrete Mathematics
Volume165-166
DOIs
StatePublished - Mar 15 1997

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'On perfect 0, ± 1 matrices 1, 2'. Together they form a unique fingerprint.

Cite this