Algorithms for Finding Tucker Patterns

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2013-01-23
Authors/Contributors
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.
Permissions
The author granted permission for the file to be printed and for the text to be copied and pasted.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Chauve, Cedric
Member of collection
Attachment Size
etd7624_MTamayo.pdf 1.3 MB