1、A simple Test For the Consecutive Ones PropertyWithout PC-trees!Consecutive 1s Property of matricesGiven a (0,1)- matrix M, does there exist a PERMUTATION of the COLUMINS of M such that the 1s in the ROWS are consecutive?1 2 3 41 1 0 01 0 0 10 1 1 03 2 1 40 1 1 00 0 1 11 1 0 0Consecutive requirement
2、 on the rows Each row i of M can be viewed as a requirement that those columns with a 1 in row j must be consecutive. Booth and Lueker 1976 showed that the consecutive ones property can be tested using P-Q trees in linear time. They process the consecutive requirement in a row by row fashion.P-Q Tre
3、esTwo types of internal nodes: P-nodes & Q-nodesChildren of a P-node can be “permuted arbitrarily”Children of a Q-node can only be “reversed”QP1 23 4L(T) = all permutations generated by T In the example, L(T) = 1234,1243,4321,3421 Intermediate On-Line Operations Strictly Overlapping RelationshipsTwo
4、 columns are say, to overlap strictly if they overlap but none is contained in the other.Such a pair of rows implies the following column partition: 1 - - - - - - 1 1 - - - 1 1 - - - - 1 uv Ideal SituationIf there is a vertex ordering v1 , v2 ,v m such that each vi strictly overlaps with some vj wit
5、h j i, then it is trivial to test the consecutive ones propertyPartitionBefore 1- - - - - - 1 1 - - - 1 1 - - - - 1 After 1 - - - 1 1 - - 1 1 - - 1 1 - - - 1 1 - - - - 1 The General Case (I) Define the graph G on the set of rows whose edge set consists of those strictly overlapping pairs of columns.
6、 Each connected component of G satisfies the above “ideal situation”.The corresponding submatrices are called prime The matrix satisfies the COP iff each of its prime submatrices doesAn example of the Graph G1234567891016437981052The General Case (II) However, we cannot afford to compute all the edges in G, which could take O(r2 ) time. We shall compute a subset of edges that contain a spanning tree of each connected component. Note that the process of obtaining the component actually decompose the matrix into prime submatrices
