Please use this identifier to cite or link to this item:
Type: Artigo de periódico
Title: On the consecutive ones property
Author: Meidanis, J
Porto, O
Telles, GP
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.
Country: Holanda
Editor: Elsevier Science Bv
Rights: fechado
Identifier DOI: 10.1016/S0166-218X(98)00078-X
Date Issue: 1998
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
WOS000077300400017.pdf1.78 MBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.