Decomposition of Balanced Matrices

Document Type

Article

Publication Title

Journal of Combinatorial Theory. Series B

Abstract

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. © 1999 Academic Press.

Publication Date

1-4-1999

Volume

Vol.77

Issue

Iss.2

Link to Full Text
Request Access

Share

COinS