×

zbMATH — the first resource for mathematics

Decomposition of balanced matrices. (English) Zbl 1023.05025
Summary: A \((0,1)\) matrix is balanced if it does not contain a square submatrix of odd order with two ones per row and per column. We show that a balanced \((0,1)\) matrix is either totally unimodular or its bipartite representation has a cutset consisting of two adjacent nodes and some of their neighbors. This result yields a polytime recognition algorithm for balancedness. To prove the result, we first prove a decomposition theorem for balanced \((0,1)\) matrices that are not strongly balanced.

MSC:
05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Anstee, R.; Farber, M., Characterization of totally balanced matrices, J. algorithms, 5, 215-230, (1984) · Zbl 0551.05026
[2] Berge, C., Sur certains hypergraphes généralisant LES graphes bipartis, (), 119-133 · Zbl 0205.54501
[3] Berge, C., Balanced matrices, Math. programming, 2, 19-31, (1972) · Zbl 0247.05126
[4] Berge, C., Graphs and hypergraphs, (1973), North Holland · Zbl 0483.05029
[5] Berge, C., Balanced matrices and the property G, Math. programming study, 12, 163-175, (1980) · Zbl 0467.05048
[6] Berge, C., Minimax theorems for normal and balanced hypergraphs. A survey, (), 3-21 · Zbl 0554.05052
[7] Berge, C., Minimax relations for the partial q-colorings of a graph, Discrete math., 74, 3-14, (1989) · Zbl 0685.05021
[8] Berge, C.; Las Vergnas, M., Sur un théorème du type König pour LES hypergraphes, Annals of the New York Academy of sciences, 175, 32-40, (1970) · Zbl 0229.05136
[9] Camion, P., Characterization of totally unimodular matrices, Proc. amer. math. soc., 16, 1068-1073, (1965) · Zbl 0134.25201
[10] Commoner, F.G., A sufficient conditions for a matrix to be totally unimodular, Networks, 3, 351-365, (1973) · Zbl 0352.05012
[11] Conforti, M.; Cornuéjols, G., A decomposition theorem for balanced matrices, (), 147-169
[12] Conforti, M.; Cornuéjols, G.; Kapoor, A.; Rao, M.R.; Vusković, K., Balanced matrices, (), 1-33
[13] M. Conforti, G. Cornuéjols, A. Kapoor, and, K. Vusković, Balanced 0, +1, −1 matrices, preprints, 1993.
[14] Conforti, M.; Cornuéjols, G.; Kapoor, A.; Vusković, K., Perfect matchings in balanced hypergraphs, Combinatorica, 16, 325-329, (1996) · Zbl 0864.05074
[15] M. Conforti, A. M. H. Gerards, and, A. Kapoor, A Theorem of Truemper, to appear. Preliminary version by M. Conforti and A. Kapoor, in, Lecture Notes in Computer Science, Integer Programming and Combinatorial Optimization, 6th IPCO Conference, Houston, pp. 53-68, 1988.
[16] Conforti, M.; Rao, M.R., Structural properties and recognition of restricted and strongly unimodular matrices, Math. programming, 38, 17-27, (1987) · Zbl 0642.90104
[17] Conforti, M.; Rao, M.R., Structural properties and decomposition of linear balanced matrices, Math. programming, 55, 129-169, (1992) · Zbl 0767.90068
[18] Conforti, M.; Rao, M.R., Odd cycles and matrices with integrality properties, Math. programming, 45, 279-295, (1989) · Zbl 0681.90078
[19] Conforti, M.; Rao, M.R., Properties of balanced and perfect matrices, Math. programming, 55, 35-49, (1992) · Zbl 0767.90067
[20] Conforti, M.; Rao, M.R., Testing balancedness and perfection of linear and star decomposable matrices, Math. programming, 61, 1-18, (1993) · Zbl 0788.90062
[21] Cornuéjols, G.; Cunningham, W.H., Compositions for perfect graphs, Discrete math., 55, 245-254, (1985) · Zbl 0562.05043
[22] Cunningham, W.H.; Edmonds, J., A combinatorial decomposition theory, Canad. J. math., 22, 734-765, (1980) · Zbl 0442.05054
[23] Fulkerson, D.R.; Hoffman, A.; Oppenheim, R., On balanced matrices, Math. programming study, 1, 120-132, (1974) · Zbl 0357.90038
[24] Golumbic, M.C.; Goss, C.F., Perfect elimination and chordal bipartite graphs, J. graph theory, 2, 155-163, (1978) · Zbl 0411.05060
[25] Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press · Zbl 0541.05054
[26] Hall, P., On representatives of subsets, J. London math. soc., 26-30, (1935) · Zbl 0010.34503
[27] Hoffman, A.; Kolen, A.; Sakarovitch, M., Characterizations of totally balanced and greedy matrices, SIAM journal of algebraic and discrete methods, 6, 721-730, (1985) · Zbl 0573.05041
[28] Schrijver, A., Theory of linear and integer programming, (1986), Wiley New York · Zbl 0665.90063
[29] Seymour, P., Decomposition of regular matroids, J. combin. theory ser. B, 28, 305-359, (1980) · Zbl 0443.05027
[30] Truemper, K., Alfa-balanced graphs and matrices and GF(3)-representability of matroids, J. combin. theory ser. B, 32, 112-139, (1982) · Zbl 0478.05026
[31] Yannakakis, M., On a class of totally unimodular matrices, Mathematics of operations research, 10, 280-304, (1985) · 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.