CMR  1.3.0
Complement Totally Unimodular Matrices

Consider a binary matrix \( M \in \{0,1\}^{m \times n} \). A row complement for row \( i \) is obtained by complementing all entries \( M_{r,c} \) with \( r \neq i \) and \( M_{i,c} = 1 \). A column complement is defined as a row complement on the transpose matrix. A binary matrix \( M \) is complement totally unimodular if all matrices obtainable by successive row- and column complements are totally unimodular. It turns out that all such matrices can be obtained already by at most one row complement and at most one column complement. Hence, complement total unimodularity can be checked by checking \( (m+1) \cdot (n+1) \) matrices for total unimodularity.

Usage

The executable cmr-ctu determines whether a given matrix \( M \) is complement totally unimodular or applies row- or column-complement operations (or both at the same time) to \( M \).

./cmr-ctu [OPTION]... FILE

Options:

Formats for matrices are dense-matrix and sparse-matrix. If FILE is -, then the input will be read from stdin. If -r or -c (or both) are specified, then \( M \) is not tested for complement total unimodularity.

C Interface

The functionality is defined in ctu.h. The main functions are: