Resource type
Thesis type
(Thesis) M.Sc.
Date created
2013-01-23
Authors/Contributors
Author: Tamayo, Maria Mercedes
Abstract
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.
Document
Identifier
etd7624
Copyright statement
Copyright is held by the author.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Chauve, Cedric
Member of collection
Download file | Size |
---|---|
etd7624_MTamayo.pdf | 1.3 MB |