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

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

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

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Consecutive retrieval property -- revisited
• 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)

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

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)