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
    0 references

    Identifiers