zbMATH — the first resource for mathematics

Structural properties and decomposition of linear balanced matrices. (English) Zbl 0767.90068
Summary: Claude Berge defines a (0,1) matrix \(A\) to be linear if \(A\) does not contain a \(2\times 2\) submatrix of all ones. A \((0,1)\) matrix \(A\) is balanced if \(A\) does not contain a square submatrix of odd order with two ones per row and column. The contraction of a row \(i\) of a matrix consists of the removal of row \(i\) and all the columns that have a 1 in the entry corresponding to row \(i\).
We show that if a linear balanced matrix \(A\) does not belong to a subclass of totally unimodular matrices, then \(A\) or \(A^ T\) contains a row \(i\) such that the submatrix obtained by contracting row \(i\) has a block-diagonal structure.

90C27 Combinatorial optimization
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
90C35 Programming involving graphs or networks
Full Text: DOI
[1] R.F. Anstee and M. Farber, ”Characterizations of totally balanced matrices,”Journal of Algorithms 5 (1984) 215–230. · Zbl 0551.05026
[2] C. Berge, ”Balanced matrices,”Mathematical Programming 2 (1972) 19–31. · Zbl 0247.05126
[3] C. Berge, ”Balanced matrices and the property G,”Mathematical Programming Study 12 (1980) 163–175. · Zbl 0467.05048
[4] C. Berge, ”Minimax theorems for normal and balanced hypergraphs: A survey,”Annals of Discrete Mathematics 21 (1984) 3–21. · Zbl 0554.05052
[5] C. Berge and M. Las Vergnas, ”Sur un theoreme du type Konig pour les hypergraphes,”Annals of New York Academy of Sciences 175 (1970) 32–40. · Zbl 0229.05136
[6] M. Conforti and M.R. Rao, ”Structural properties and decomposition of restricted and strongly unimodular matrices,”Mathematical Programming 38 (1987a) 17–27. · Zbl 0642.90104
[7] M. Conforti and M.R. Rao, ”Odd cycles and 0, 1 matrices,” to appear in:Mathematical Programming (series B) (1987b). · Zbl 0642.90104
[8] M. Conforti and M.R. Rao, ”Testing balancedness and perfection of linear graphs,” preprint, New York University (New York, 1988). · Zbl 0788.90062
[9] J. Fonlupt and A. Zemirline, ”A polynomial recognition algorithm for perfect (K 4–e)-free perfect graphs,” Research Report, University of Grenoble (Grenoble, 1987).
[10] A. Frank, ”On a class of balanced hypergraphs,” mimeo, Research Institute for Telecommunications (Budapest, 1979).
[11] D.R. Fulkerson, A.J. Hoffman and R. Oppenheim, ”On balanced matrices,”Mathematical Programming Study 1 (1974), 120–132. · Zbl 0357.90038
[12] A. Hoffman, A. Kolen and M. Sakarovitch, ”Totally balanced and greedy matrices,”SIAM Journal of Algebraic and Discrete Methods 6 (1985) 721–730. · Zbl 0573.05041
[13] M. Padberg, ”Characterizations of totally unimodular, balanced and perfect matrices,”Combinatorial Programming, Methods and Applications (1975) 279–289. · Zbl 0316.90045
[14] P.D. Seymour, ”Decomposition of regular matroids,”Journal of Combinatorial Theory B-28 (1980) 305–359. · Zbl 0443.05027
[15] M. Yannakakis, ”On a class of totally unimodular matrices,”Mathematics of Operations Research 10 (2) (1985) 280–304. · Zbl 0565.90042
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.