A faster algorithm for finding minimum Tucker submatrices

DOI10.1007/S00224-012-9388-1MaRDI QIDQ693064zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

consecutive ones propertyTucker configurations

Mathematics Subject Classification ID

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

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)

Cites work

• scientific article; zbMATH DE number 1003281 (Why is no real title available?)
• scientific article; zbMATH DE number 5606342 (Why is no real title available?)
• scientific article; zbMATH DE number 1187154 (Why is no real title available?)
• A Simple Test for the Consecutive Ones Property
• A Spectral Algorithm for Seriation and the Consecutive Ones Problem
• A certifying algorithm for the consecutive-ones property
• A faster algorithm for finding minimum Tucker submatrices
• A note on the consecutive ones submatrix problem.
• A polynomial-time algorithm for finding a minimal conflicting set containing a given row
• Algorithms – ESA 2004
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Approximation algorithms for hitting objects with straight lines
• Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
• Cyclic Scheduling via Integer Programs with Circular Ones
• Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms
• Incidence matrices and interval graphs
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• On Physical Mapping and the consecutive ones property for sparse matrices
• On the complexity of testing for odd holes and induced odd paths
• On the consecutive ones property
• On the gapped consecutive-ones property
• Optimal Capacity Scheduling—I
• PC trees and circular-ones arrangements.
• Polynomial Complete Consecutive Information Retrieval Problems
• Set covering with almost consecutive ones property
• Station location -- complexity and approximation
• Structural properties and decomposition of linear balanced matrices
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The consecutive ones submatrix problem for sparse matrices
• The simultaneous consecutive ones problem

Cited in

(7)

• Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs
• Faster and simpler minimal conflicting set identification (extended abstract)
• Obtaining matrices with the consecutive ones property by row deletions
• Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results
• A faster algorithm for finding minimum Tucker submatrices
• A polynomial-time algorithm for finding a minimal conflicting set containing a given row
• On finding Tucker submatrices and Lekkerkerker-Boland subgraphs

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)