A note on the consecutive ones submatrix problem.

DOI10.1016/S0020-0190(01)00325-8MaRDI QIDQ1853060zbMATH OpenOpenAlexFDO

Authors Mohammad T. Hajiaghayi, Yashar Ganjali

Publication date 21 January 2003

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(01)00325-8

zbMATH Keywords

Computational complexityConsecutive Ones PropertyConsecutive Ones Submatrix

Mathematics Subject Classification ID

Matrices of integers (15B36) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

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)].

Recommendations

• scientific article; zbMATH DE number 3848609
• The consecutive ones submatrix problem for sparse matrices
• Algorithms and Computation
• scientific article; zbMATH DE number 5606342
• Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results

Cites work

• Consecutive retrieval property -- revisited
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Incidence matrices and interval graphs
• Interval routing schemes
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• On testing consecutive-ones property in parallel
• On the consecutive ones property
• Polynomial Complete Consecutive Information Retrieval Problems
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Cited in

(10)

• Hardness results on the gapped consecutive-ones property problem
• Obtaining matrices with the consecutive ones property by row deletions
• Minimising the number of gap-zeros in binary matrices
• On the gapped consecutive-ones property
• Defragmentation of permutation tables with four columns
• scientific article; zbMATH DE number 3848609 (Why is no real title available?)
• A structural characterization for certifying Robinsonian matrices
• Temporal interval cliques and independent sets
• A faster algorithm for finding minimum Tucker submatrices
• Approximation and fixed-parameter algorithms for consecutive ones submatrix problems

This page was built for publication: A note on the consecutive ones submatrix problem.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853060)