On the consecutive ones property

A binary matrix has the Consecutive Ones Property (C1P) 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 str...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 1998-11, Vol.88 (1), p.325-354
Main Authors: Meidanis, João, Porto, Oscar, Telles, Guilherme P.
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A binary matrix has the Consecutive Ones Property (C1P) 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 C1P, 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.
ISSN:0166-218X
1872-6771
DOI:10.1016/S0166-218X(98)00078-X