Title:  Tractability Results for the ConsecutiveOnes Property with Multiplicity 
Speaker: 
Murray Patterson Department of Computer Science, UBC 
Abstract 
A binary matrix M has the ConsecutiveOnes Property (C1P) if its
columns can be ordered in such a way that all 1's in each row are
consecutive. We consider here a variant of the C1P where columns can
appear multiple times in the ordering (the multiplicity of a column is
the number of times it appears in M). Although the general problem of
deciding the C1P with multiplicity is NPcomplete, we present here a
case of interest in comparative genomics that is tractable.
