2012/01/26 by Aïda Ouangraoua, Aida Ouangraoua, Ouangraoua, Aida +2
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genome Rearrangement Algorithms #cs.DS #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1201.5513
arxiv created 2012/01/26 · openalex publication_date 2012/01/26 · arxiv updated 2012/01/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let C be a finite set of N elements and R = r1,r2,..., rm a family of M subsets of C. A subset X of R verifies the Consecutive Ones Property (C1P) if there exists a permutation P of C such that each ri in X is an interval of P. A Minimal Conflicting Set (MCS) S is a subset of R that does not verify the C1P, but such that any of its proper subsets does. In this paper, we present a new simpler and faster algorithm to decide if a given element r in R belongs to at least one MCS. Our algorithm runs in O(N2M2 + NM7), largely improving the current O(M6N5 (M+N)2 log(M+N)) fastest algorithm of [Blin \em et al, CSR 2011]. The new algorithm is based on an alternative approach considering minimal forbidden induced subgraphs of interval graphs instead of Tucker matrices.