ISSN:
1436-4646
Keywords:
Polyhedral combinatorics
;
integrality of polytopes
;
decomposition
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract Claude Berge defines a (0, 1) matrix A to be linear ifA does not contain a 2 × 2 submatrix of all ones.A(0, 1) matrixA is balanced ifA does not contain a square submatrix of odd order with two ones per row and column. The contraction of a rowi of a matrix consists of the removal of rowi and all the columns that have a 1 in the entry corresponding to rowi. In this paper we show that if a linear balanced matrixA does not belong to a subclass of totally unimodular matrices, thenA orA T contains a rowi such that the submatrix obtained by contracting rowi has a block-diagonal structure.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01581196
Permalink
