Skip to Main content Skip to Navigation
Journal articles

A faster algorithm for finding minimum Tucker submatrices

Abstract : A binary matrix has the Consecutive Ones Property (C1P) if its columns can be ordered in such a way that all 1s on each row are consecutive. Algorithmic issues of the C1P are central in computational molecular biology, in particular for physical mapping and ancestral genome reconstruction. In 1972, Tucker gave a characterization of matrices that have the C1P by a set of forbidden submatrices, and a substantial amount of research has been devoted to the problem of efficiently finding such a minimum size forbidden submatrix. This paper presents a new O(Δ³m²(mΔ+n³)) time algorithm for this particular task for a m×n binary matrix with at most Δ 1-entries per row, thereby improving the O(Δ³m²(mn+n³)) time algorithm of M. Dom, J. Guo and R. Niedermeier [Approximation and fixed-parameter algorithms for consecutive ones submatrix problems, Journal of Computer and System Sciences, 76(3-4): 204-221, 2010]. Moreover, this approach can be used - with a much heavier machinery - to address harder problems related to Minimal Conflicting Set [G. Blin, R. Rizzi, and S. Vialette. A Polynomial-Time Algorithm for Finding Minimal Conflicting Sets, Proc. 6th International Computer Science Symposium in Russia (CSR), [2011]].
Complete list of metadatas

Cited literature [35 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00657340
Contributor : Guillaume Blin <>
Submitted on : Friday, March 16, 2012 - 11:49:30 AM
Last modification on : Wednesday, February 26, 2020 - 7:06:07 PM
Long-term archiving on: : Tuesday, December 13, 2016 - 8:10:18 PM

File

hal.pdf
Files produced by the author(s)

Identifiers

Citation

Guillaume Blin, Romeo Rizzi, Stéphane Vialette. A faster algorithm for finding minimum Tucker submatrices. Theory of Computing Systems, Springer Verlag, 2012, 51 (3), pp.270-281. ⟨10.1007/s00224-012-9388-1⟩. ⟨hal-00657340⟩

Share

Metrics

Record views

508

Files downloads

590