Skip to Main content Skip to Navigation
Conference papers

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 computa- tional molecular biology, in particular for physical mapping and ances- tral 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 ef- ciently nding such a minimum size forbidden submatrix. This paper presents a new O( 3m2 (m + n 3 )) time algorithm for this particular task for a m n binary matrix with at most 1-entries per row, thereby improving the O( 3m2 (mn + n 3 )) time algorithm of Dom et al. [17].
Document type :
Conference papers
Complete list of metadatas

Cited literature [36 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00620380
Contributor : Guillaume Blin <>
Submitted on : Friday, September 30, 2011 - 3:48:11 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:06 PM
Long-term archiving on: : Tuesday, November 13, 2012 - 2:57:20 PM

File

hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00620380, version 1

Citation

Guillaume Blin, Romeo Rizzi, Stéphane Vialette. A faster algorithm for finding minimum Tucker submatrices. 6th Computability in Europe (CiE'10), 2010, Portugal. pp.69-77. ⟨hal-00620380⟩

Share

Metrics

Record views

675

Files downloads

490