On matrices that do not have the consecutive ones property

Resource type
Thesis type
(Thesis) M.Sc.
Date created
A binary matrix has the consecutive ones property if its columns can be ordered in such a way that, in each row, all 1s are consecutive. This classical combinatorial notion has been central in genomic problems such as physical mapping or paleogenomics. In these fields, genomes that cannot be sequenced are represented by a matrix that has the consecutive ones property, but are inferred from an initial matrix that does not have this property due to errors. In this work, we study combinatorial and algorithmic characterizations of matrices that do not have the consecutive ones property. We review existing results and propose new results centered around the notion of minimal conflicting sets.
Copyright statement
Copyright is held by the author.
Scholarly level
Member of collection
Attachment Size
ETD4658.pdf 914.56 KB