Back to BMAC Page
THE CONSECUTIVE-ONES PROPERTY
A consecutive-ones ordering of a 0-1 matrix is a reordering of the
columns so that, in every row, the 1's form a consecutive block. There
are well-known algorithms for finding a consecutive-ones ordering if one
exist, but when one doesn't exist, they simply declare that it is
impossible, without supplying any documentation of this claim.
Though these algorithms have been proven correct, this raises
a software-engineering challenge: if you cannot be sure that software
that implements the algorithm is bug-free, how can you be sure that it
has answered truthfully when it claims that a consecutive-ones ordering is
impossible?
We give a characterization of matrices that have the consecutive-ones
property in terms of a forbidden substructure. We give an algorithm that
either returns a consecutive-ones ordering or the forbidden substructure,
which proves that a consecutive-ones ordering is impossible. This allows
a skeptical user to be certain that the output to an instance of the
problem has not been compromised by a bug.
The characterization also gives rise to a recursive decomposition of
arbitrary 0-1 matrices that has not been described previously.
Back to BMAC Page