A note on the Consecutive Ones Submatrix problem |
| |
Authors: | Mohammad Taghi Hajiaghayi Yashar Ganjali |
| |
Affiliation: | Department of Computer Science, University of Waterloo, Waterloo, ON, Canada N2L 3GI |
| |
Abstract: | 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 Garey and Johnson Computers and Intractability, A Guide to the Theory of NP-Completeness, 1979]. |
| |
Keywords: | Computational complexity Consecutive Ones Property Consecutive Ones Submatrix |
本文献已被 ScienceDirect 等数据库收录! |