Decomposition of Balanced Matrices. Part 4. Connected Squares
Abstract
There exist two complete bipartite graphs K1, K2 in G having disjoint node sets, with the property that the removal of the edges in K1, K2 disconnects G. There exists a subset S of the nodes of G with the property that the removal of S disconnects G, where S can be partitioned into three disjoint sets T,A,N such that T is not equal to 0 some nodes T is adjacent to every node and every node of T is adjacent to every node of A. 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. Balanced matrices are important in integer programming and combinatorial optimization since the associated set packing and set covering polytopes have integral vertices. To a 0,1 matrix A we associate a bipartite graph as follows: The node nets Vr and Vc represent the row set and the column set of A and edge ij belongs to E if and only if ay=1. Since a 0,1 matrix is balanced if and only if the associated bipartite graph does not contain a chordless cycle of length 4k+2, the above theorem provides a decomposition of balanced matrices into elementary matrices whose associated bipartite graphs have no cycle of length 4k + 2.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1991
- Accession Number
- ADA247308
Entities
People
- Gérard Cornuéjols
- M. R. Rao
- Michele Conforti
Organizations
- Carnegie Mellon University