A faster algorithm for finding minimum Tucker submatrices
DOI10.1007/S00224-012-9388-1zbMATH Open1252.92003OpenAlexW2030520663MaRDI QIDQ693064FDOQ693064
Authors: Guillaume Blin, Romeo Rizzi, Stéphane Vialette 
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
Recommendations
- A faster algorithm for finding minimum Tucker submatrices
- Minimal Conflicting Sets for the Consecutive Ones Property in Ancestral Genome Reconstruction
- Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs
- A polynomial-time algorithm for finding a minimal conflicting set containing a given row
- Faster and simpler minimal conflicting set identification (extended abstract)
Biochemistry, molecular biology (92C40) Analysis of algorithms (68W40) Computational methods for problems pertaining to biology (92-08) Algorithms in computer science (68W99)
Cites Work
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Incidence matrices and interval graphs
- A Spectral Algorithm for Seriation and the Consecutive Ones Problem
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
- Title not available (Why is that?)
- Cyclic Scheduling via Integer Programs with Circular Ones
- Approximation algorithms for hitting objects with straight lines
- Optimal Capacity Scheduling—I
- PC trees and circular-ones arrangements.
- A Simple Test for the Consecutive Ones Property
- Title not available (Why is that?)
- Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
- Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the consecutive ones property
- Set covering with almost consecutive ones property
- Station location -- complexity and approximation
- Algorithms – ESA 2004
- A note on the consecutive ones submatrix problem.
- On the complexity of testing for odd holes and induced odd paths
- The simultaneous consecutive ones problem
- Structural properties and decomposition of linear balanced matrices
- Polynomial Complete Consecutive Information Retrieval Problems
- The consecutive ones submatrix problem for sparse matrices
- On the gapped consecutive-ones property
- A polynomial-time algorithm for finding a minimal conflicting set containing a given row
- A faster algorithm for finding minimum Tucker submatrices
- On Physical Mapping and the consecutive ones property for sparse matrices
Cited In (6)
- A faster algorithm for finding minimum Tucker submatrices
- Obtaining matrices with the consecutive ones property by row deletions
- A polynomial-time algorithm for finding a minimal conflicting set containing a given row
- Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs
- Faster and simpler minimal conflicting set identification (extended abstract)
- Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results
This page was built for publication: A faster algorithm for finding minimum Tucker submatrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q693064)
