Name
Abstract | ||
|---|---|---|
The Consecutive Ones Property is an important notion for binary matrices, both from a theoretical and applied point of view. Tucker gave in 1972 a characterization of matrices that do not satisfy the Consecutive Ones Property in terms of forbidden submatrices, the Tucker patterns. We describe here a linear time algorithm to find a Tucker pattern in a non-C1P binary matrix, which allows to extract in linear time a certificate for the non-C1P. We also describe an output-sensitive algorithm to enumerate all Tucker patterns of a non-C1P binary matrix. This paper had been withdrawn due to some missing cases in Algorithms 2 and 3. |
Year | Venue | Field |
|---|---|---|
2012 | CoRR | Discrete mathematics,Combinatorics,Logical matrix,Matrix (mathematics),Algorithm,Time complexity,Block matrix,Mathematics,Binary number,Certificate |
DocType | Volume | Citations |
Journal | abs/1206.1837 | 0 |
PageRank | References | Authors |
0.34 | 6 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| cedric chauve | 1 | 429 | 41.81 |
| Tamon Stephen | 2 | 121 | 16.03 |
| Maria Tamayo | 3 | 0 | 0.34 |