A faster algorithm for finding minimum Tucker submatrices

DOI10.1007/s00224-012-9388-1zbMath1252.92003OpenAlexW2030520663MaRDI QIDQ693064

Romeo Rizzi, Stéphane Vialette, Guillaume Blin

Publication date: 7 December 2012

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-012-9388-1

zbMATH Keywords

consecutive ones propertyTucker configurations

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Biochemistry, molecular biology (92C40) Computational methods for problems pertaining to biology (92-08) Algorithms in computer science (68W99)

Related Items

Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results ⋮ Obtaining matrices with the consecutive ones property by row deletions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms
• Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
• The simultaneous consecutive ones problem
• Approximation algorithms for hitting objects with straight lines
• On the complexity of testing for odd holes and induced odd paths
• Structural properties and decomposition of linear balanced matrices
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On the consecutive ones property
• 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.
• Set covering with almost consecutive ones property
• Incidence matrices and interval graphs
• The consecutive ones submatrix problem for sparse matrices
• On the Gapped Consecutive-Ones Property
• Station Location - Complexity and Approximation.
• A Polynomial-Time Algorithm for Finding a Minimal Conflicting Set Containing a Given Row
• A Simple Test for the Consecutive Ones Property
• A Faster Algorithm for Finding Minimum Tucker Submatrices
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Optimal Capacity Scheduling—I
• Cyclic Scheduling via Integer Programs with Circular Ones
• Polynomial Complete Consecutive Information Retrieval Problems
• A Spectral Algorithm for Seriation and the Consecutive Ones Problem
• Algorithms – ESA 2004
• On Physical Mapping and the consecutive ones property for sparse matrices