Lehman's forbidden minor characterization of ideal 0-1 matrices

DOI10.1016/0012-365X(93)90178-VMaRDI QIDQ686505zbMATH OpenFDO

Authors Manfred Padberg

Publication date 20 December 1993

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(93)90178-V

zbMATH Keywords

ideal matriceszero-one matrices

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Matrices over special rings (quaternions, finite fields, etc.) (15B33)

Review text

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.

Recommendations

• (0, 1) ideal matrices
• A new infinite family of minimally nonideal matrices
• \((0, \pm 1)\) ideal matrices
• Ideal 0, 1 matrices
• Applying Lehman's theorems to packing problems

Cites work

• Almost integral polyhedra related to certain combinatorial optimization problems
• An extension of a theorem of the Bruijn and Erdős on combinatorial designs
• Blocking and anti-blocking pairs of polyhedra
• scientific article; zbMATH DE number 3495859 (Why is no real title available?)
• scientific article; zbMATH DE number 3513556 (Why is no real title available?)
• scientific article; zbMATH DE number 3628968 (Why is no real title available?)
• Normal hypergraphs and the perfect graph conjecture
• On the width—length inequality
• Perfect zero–one matrices

Cited in

(22)

• On the set covering polyhedron of circulant matrices
• A characterization of knapsacks with the max-flow--min-cut property
• A catalog of minimally nonideal matrices
• Ideal 0, 1 matrices
• A note on clutter partitions
• Subsets of a finite set that almost always intersect each other in elements
• (0, 1) ideal matrices
• Non-regular square bipartite designs
• On the mixed set covering, packing and partitioning polytope
• A characterization of weakly bipartite graphs
• A short proof of Guenin's characterization of weakly bipartite graphs
• Applying Lehman's theorems to packing problems
• Structure of cubic Lehman matrices
• Some insight into characterizations of minimally nonideal matrices
• On a certain class of nonideal clutters
• \((0, \pm 1)\) ideal matrices
• A class of polynomially solvable 0-1 programming problems and an application
• scientific article; zbMATH DE number 2230198 (Why is no real title available?)
• Minimal nonnegative integral matrices and uniquely determined (0,1)-matrices
• Ideal clutters
• The nonidealness index of rank-ideal matrices
• Efficient solutions for special zero-one programming problems

This page was built for publication: Lehman's forbidden minor characterization of ideal 0-1 matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q686505)