A faster algorithm for finding minimum Tucker submatrices
From MaRDI portal
Publication:693064
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
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
