Lehman's forbidden minor characterization of ideal 0-1 matrices (Q686505)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Lehman's forbidden minor characterization of ideal 0-1 matrices |
scientific article |
Statements
Lehman's forbidden minor characterization of ideal 0-1 matrices (English)
0 references
20 December 1993
0 references
An \(m\times n\) (0,1)-matrix is called ideal if the polyhedron \(P(A):= \{x\in \mathbb{R}^ n: Ax\geq e,\;x\geq 0\) (componentwise)\} is nonempty and all of its extreme points are integer-valued, where \(e= (1,\dots,1)^ T\). In 1979 A. Lehman gave characterizations of minimally nonideal (0,1)- matrices which remained unpublished. In the paper under review, the author presents both a documentation of Lehman's investigations and a different proof of the complete characterization of all minimally (almost) nonideal matrices.
0 references
zero-one matrices
0 references
ideal matrices
0 references