Obtaining matrices with the consecutive ones property by row deletions

DOI10.1007/s00453-014-9925-1zbMath1312.68106OpenAlexW2077851352MaRDI QIDQ2343088

N. S. Narayanaswamy, R. Subashini

Publication date: 4 May 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-014-9925-1

zbMATH Keywords

parameterized complexityconsecutive ones propertyconsecutive ones submatrix

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Temporal interval cliques and independent sets, Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results, Cyclic arrangements with minimum modulo \(m\) winding numbers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A faster algorithm for finding minimum Tucker submatrices
• Improved upper bounds for vertex cover
• A new characterization of matrices with the consecutive ones property
• Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
• The node-deletion problem for hereditary properties is NP-complete
• Some simplified NP-complete graph problems
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On the consecutive ones property
• On the complexity of DNA physical mapping
• PC trees and circular-ones arrangements.
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• A note on the consecutive ones submatrix problem.
• Algorithmic graph theory and perfect graphs
• Incidence matrices and interval graphs
• Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• A structure theorem for the consecutive 1's property
• The consecutive ones submatrix problem for sparse matrices
• On Finding Tucker Submatrices and Lekkerkerker-Boland Subgraphs
• FPT Algorithms for Consecutive Ones Submatrix Problems
• Consecutive Ones Property Testing: Cut or Swap
• A Simple Test for the Consecutive Ones Property
• A Spectral Algorithm for Seriation and the Consecutive Ones Problem
• Interval Deletion is Fixed-Parameter Tractable
• File organization
• On Physical Mapping and the consecutive ones property for sparse matrices