BALANCED 0,+ -1-MATRICES, BICOLORING AND TOTAL DUAL INTEGRALITY/

Authors
CONFORTI M CORNUEJOLS G
Citation
M. Conforti et G. Cornuejols, BALANCED 0,+ -1-MATRICES, BICOLORING AND TOTAL DUAL INTEGRALITY/, Mathematical programming, 71(3), 1995, pp. 249-258
Citations number
19
Categorie Soggetti
Operatione Research & Management Science",Mathematics,"Operatione Research & Management Science",Mathematics,"Computer Science Software Graphycs Programming
Journal title
Mathematical programming → ACNP
ISSN journal
00255610
Volume
71
Issue
3
Year of publication
1995
Pages
249 - 258
Database
ISI
SICI code
0025-5610(1995)71:3<249:B0-BAT>2.0.ZU;2-6
Abstract
A 0, +/-1-matrix A is balanced if, in every submatrix with two nonzero entries per row and column, the sum of the entries is a multiple of f our. This definition was introduced by Truemper (1978) and generalizes the notion of a balanced 0, 1-matrix introduced by Berge (1970). In t his paper, we extend a bicoloring theorem of Berge (1970) and total du al integrality results of Fulkerson, Hoffman and Oppenheim (1974) to b alanced 0, +/-1-matrices.