A faster algorithm for finding minimum Tucker submatrices

Guillaume Blin (1) , Romeo Rizzi (2) , Stéphane Vialette (1)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 DIMI - Dipartimento di Matematica e Informatica - Universita Udine

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].

Domaines: Algorithme et structure de données [cs.DS]

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⟩