Algorithms for Finding Tucker Patterns

The Consecutive-Ones Property (C1P) in binary matrices is a combinatorial concept with applications in several area, from graph planarity testing to computational biology. Tucker patterns are families of submatrices that characterize non-C1P matrices, and thus represent natural certificates of non-C1P matrices. However, there are very few algorithmic results regarding Tucker patterns. In the present work, that is part of a systematic study of Tucker patterns, we present several algorithmic and structural results about Tucker patterns in binary matrices that do not satisfy the C1P. The results obtained are the following: An output-sensitive enumeration algorithm for Tucker patterns; a detailed study of the link between partition refinement and Tucker patterns.