✦ LIBER ✦

Ideal 0, 1 Matrices

✍ Scribed by G. Cornuejols; B. Novick

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 533 KB
Volume: 60
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1994.1009

No coin nor oath required. For personal study only.

✦ Synopsis

We define a 0,1 matrix (M) to be ideal if all vertices of the polyhedron ({x: M x \geqslant 1), (x \geqslant 0}) have only 0,1 components. We expand the list of known minor minimal nonideal matrices by several thousand. Many of these examples are obtained polyhedrally, by constructing new minimally nonideal matrices from old ones. We present a conjecture that might be viewed as the counterpart for ideal matrices of Berge's strong perfect graph conjecture. We provide evidence for the conjecture by completely characterizing all minimally nonideal circulants. "T 1994 Academic Press, Inc.

📜 SIMILAR VOLUMES

Lehman's forbidden minor characterizatio

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

✍ Manfred Padberg 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 765 KB

A zero-one matrix is ideal if its associated covering polyhedron is integral. In this note we document the proof of a lemma of A. Lehman that was communicated to us by U. Peled in 1979 and that characterizes square minimally nonideal zero-one matrices completely. We then give a somewhat different pr

Balanced 0, ±1 Matrices I. Decomposition

✍ Michele Conforti; Gérard Cornuéjols; Ajai Kapoor; Kristina Vušković 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 287 KB

A 0, \1 matrix is balanced if, in every square submatrix with two nonzero entries per row and column, the sum of the entries is a multiple of four. This paper extends the decomposition of balanced 0, 1 matrices obtained by Conforti, Cornue jols, and Rao (1999, J. Combin. Theory Ser. B 77, 292 406) t

Classification de certaines matrices 0–1

✍ J.D. MacAllister; M. Sakarovitch 📂 Article 📅 1977 🏛 Elsevier Science 🌐 English ⚖ 723 KB

This paper is a survey of the main propertics of special O-1 matrices. All thcsc prcrpertles are presented in a unified bmework (in terms of matrices and not in terms of hypergraphs). The paper contains no original result and no proof. NuI doute que I'une des idles de Bcrge quand il a introduit le c

Permanents of 0,1-matrices

✍ B Gordon; T.S Motzkin; L Welch 📂 Article 📅 1974 🏛 Elsevier Science 🌐 English ⚖ 500 KB

Geometric matrices and an inequality for

Geometric matrices and an inequality for (0,1)-matrices

✍ Lewis E. Varga 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 874 KB

Balanced 0, ±1 Matrices II. Recognition

Balanced 0, ±1 Matrices II. Recognition Algorithm

✍ Michele Conforti; Gérard Cornuéjols; Ajai Kapoor; Kristina Vušković 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 232 KB

In this paper we give a polynomial time recognition algorithm for balanced 0, \1 matrices. This algorithm is based on a decomposition theorem proved in a companion paper.