Carnegie Mellon University
Decomposition of Balanced Matrices.pdf.pdf' (753.2 kB)
Download file

Decomposition of Balanced Matrices

Download (753.2 kB)
journal contribution
posted on 1986-01-01, 00:00 authored by Michele Conforti, Gerard CornuejolsGerard Cornuejols, M. R. Rao
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.




Usage metrics