A note on the consecutive ones submatrix problem.
type: Item
instance of: scholarly article
title: A note on the consecutive ones submatrix problem.
zbMATH Open document ID: 1043.68064
DOI: 10.1016/S0020-0190(01)00325-8
author: Mohammad T. Hajiaghayi
author: Yashar Ganjali
published in: Information Processing Letters
publication date: 2003-01-21T00:00:00Z
review text: 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 \textit{M. R. Garey} and \textit{D. S. Johnson} [Computers and Intractability, A Guide to the Theory of NP-Completeness (1979)].
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 15B36
Mathematics Subject Classification ID: 68R05
zbMATH DE Number: 1856403
zbMATH Keywords: Computational complexity
zbMATH Keywords: Consecutive Ones Property
zbMATH Keywords: Consecutive Ones Submatrix
MaRDI profile type: Publication
cites work: On the consecutive ones property
cites work: Incidence matrices and interval graphs
cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
cites work: Consecutive retrieval property -- revisited
cites work: On testing consecutive-ones property in parallel
cites work: Q4198056
cites work: Polynomial Complete Consecutive Information Retrieval Problems
cites work: Interval routing schemes
cites work: Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
full work available at URL: s0020-0190(01)00325-8
OpenAlex ID: W2065242306
description: scientific article; zbMATH DE number 1856403