A note on the consecutive ones submatrix problem. (English) Zbl 1043.68064
A binary matrix has the Consecutive Ones Property (C1P) for columns if there exists a permutation of its rows that leaves the 1’s consecutive in every column. The problem of Consecutive Ones Property for a matrix is a special variant of Consecutive Ones Submatrix problem in which a positive integer \(K\) is given and we want to know if there exists a submatrix \(B\) of \(A\) consisting of \(K\) columns of \(A\) with C1P property. This paper presents an error in the proof of NP-completeness for this problem in the reference cited in text by M. R. Garey and D. S. Johnson [Computers and Intractability, A Guide to the Theory of NP-Completeness (1979)].
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 15B36 | Matrices of integers |
| 68R05 | Combinatorics in computer science |
References:
| [1] | Meidanis, J.; Porto, O.; Telles, G. P., On the consecutive ones property, Discrete Appl. Math., 88, 325-354 (1998) · Zbl 0918.05045 |
| [2] | Fulkerson, D. R.; Gross, O. A., Incidence matrices and interval graphs, Pacific J. Math., 15, 835-855 (1965) · Zbl 0132.21001 |
| [3] | Booth, K. S.; Lueker, G. S., Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. Comput. Systems Sci., 13, 3, 335-379 (1976) · Zbl 0367.68034 |
| [4] | Deogun, J. S.; Gopalakrishnan, K., Consecutive retrieval property-revisited, Inform. Process. Lett., 69, 15-20 (1999) · Zbl 1339.68071 |
| [5] | Annexstein, F.; Swaminathan, R., On testing consecutive-ones property in parallel, Discrete Appl. Math., 88, 7-28 (1998) · Zbl 0936.68111 |
| [6] | Garey, M. R.; Johnson, D. S., Computers and Intractability, A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Co.: W.H. Freeman and Co. New York · Zbl 0411.68039 |
| [7] | Kou, L. T., Polynomial complete consecutive information retrieval problems, SIAM J. Comput., 6, 67-75 (1977) · Zbl 0354.68036 |
| [8] | Flammini, M.; Gambosi, G.; Salomone, S., Boolean Routing, Lecture Notes in Comput. Sci., 725 (1993), Springer: Springer Berlin · Zbl 0860.68014 |
| [9] | Habib, M.; McConnell, R.; Paul, C.; Viennot, L., Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing, Theoret. Comput. Sci., 234, 59-84 (2000) · Zbl 0945.68189 |
| [10] | K.S. Booth, PQ-tree algorithms, Doctoral Thesis, Dept. of Electrical Engineering and Computer Science, University of California, Berkeley, CA; K.S. Booth, PQ-tree algorithms, Doctoral Thesis, Dept. of Electrical Engineering and Computer Science, University of California, Berkeley, CA |
| [11] | K.S. Booth, Private communication in UBC; K.S. Booth, Private communication in UBC |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
