Please use this identifier to cite or link to this item:
|Type:||Artigo de periódico|
|Title:||On the consecutive ones property|
|Abstract:||A binary matrix has the Consecutive Ones Property (CIP) when there is a permutation of its rows that leaves the 1's consecutive in every column. We study the recognition problem for these matrices, giving a structure, PQR trees, generalizing the PQ trees of Booth and Lueker (1976). This new structure is capable of, not only recording all valid permutations when the matrix has the CIP, but also pointing out possible obstructions when the property does not hold. We recast the problem using collections of sets, developing a new theory for it. This problem appears naturally in several applications in molecular biology, for instance, in the construction of physical maps from hybridization data. (C) 1998 Elsevier Science B.V. All right reserved.|
|Editor:||Elsevier Science Bv|
|Appears in Collections:||Unicamp - Artigos e Outros Documentos|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.