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 metadata

Cited literature [36 references]  Display  Hide  Download
Contributor : Guillaume Blin Connect in order to contact the contributor
Submitted on : Friday, September 30, 2011 - 3:48:11 PM
Last modification on : Saturday, January 15, 2022 - 3:58:22 AM
Long-term archiving on: : Tuesday, November 13, 2012 - 2:57:20 PM


Files produced by the author(s)


  • HAL Id : hal-00620380, version 1


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⟩



Record views


Files downloads