A note on the consecutive ones submatrix problem.

DOI10.1016/S0020-0190(01)00325-8zbMath1043.68064OpenAlexW2065242306MaRDI QIDQ1853060

Yashar Ganjali, Mohammad Taghi Hajiaghayi

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

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

Related Items (9)

Temporal interval cliques and independent sets ⋮ Defragmentation of permutation tables with four columns ⋮ A structural characterization for certifying Robinsonian matrices ⋮ A faster algorithm for finding minimum Tucker submatrices ⋮ Hardness results on the gapped consecutive-ones property problem ⋮ Approximation and fixed-parameter algorithms for consecutive ones submatrix problems ⋮ On the Gapped Consecutive-Ones Property ⋮ Obtaining matrices with the consecutive ones property by row deletions ⋮ Minimising the number of gap-zeros in binary matrices

Cites Work

• Unnamed Item
• Consecutive retrieval property -- revisited
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On testing consecutive-ones property in parallel
• On the consecutive ones property
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Incidence matrices and interval graphs
• Polynomial Complete Consecutive Information Retrieval Problems
• Interval routing schemes

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