zbMATH — the first resource for mathematics

Balanced \(0,\pm 1\) matrices. II: Recognition algorithm. (English) Zbl 1026.05017
Summary: We give a polynomial time recognition algorithm for balanced \(0\), \(\pm 1\) matrices. This algorithm is based on a decomposition theorem proved in a companion paper; cf. the authors [ibid. 81, 243-274 (2001; Zbl 1026.05016)].

05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
05C22 Signed and weighted graphs
Full Text: DOI
[1] M. Conforti, G. Cornuéjols, A. Kapoor, and, K. Vušković, Balanced 0, ±1 matrices. I. Decomposition, J. Combin. Theory Ser. B, in press;.
[2] Conforti, M.; Cornuéjols, G.; Kapoor, A.; Vušković, K., Balanced matrices, (), 1-33
[3] Conforti, M.; Cornuéjols, G.; Rao, M.R., Decomposition of balanced matrices, J. combin. theory ser. B, 77, 292-406, (1999) · Zbl 1023.05025
[4] Conforti, M.; Rao, M.R., Properties of balanced and perfect matrices, Math. programming, 55, 35-47, (1992) · Zbl 0767.90067
[5] Conforti, M.; Rao, M.R., Structural properties and recognition of restricted and strongly unimodular matrices, Math. programming, 38, 17-27, (1987) · Zbl 0642.90104
[6] Cornuéjols, G.; Cunningham, W.H., Compositions for perfect graphs, Discrete math., 55, 245-254, (1985) · Zbl 0562.05043
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.