Finding the Anticover of a String - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2020

Finding the Anticover of a String

Résumé

A k-anticover of a string x is a set of pairwise distinct factors of x of equal length k, such that every symbol of x is contained into an occurrence of at least one of those factors. The existence of a k-anticover can be seen as a notion of non-redundancy, which has application in computational biology, where they are associated with various non-regulatory mechanisms. In this paper we address the complexity of the problem of finding a k-anticover of a string x if it exists, showing that the decision problem is NP-complete on general strings for k ≥ 3. We also show that the problem admits a polynomial-time solution for k = 2. For unbounded k, we provide an exact exponential algorithm to find a k-anticover of a string of length n (or determine that none exists), which runs in O*(min{3 n−k 3 , (k(k+1) 2) n k+1}) time using polynomial space.
Fichier principal
Vignette du fichier
LIPIcs-CPM-2020-2.pdf (566.09 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02957658 , version 1 (05-10-2020)

Identifiants

Citer

Mai Alzamel, Alessio Conte, Shuhei Denzumi, Roberto Grossi, Costas S Iliopoulos, et al.. Finding the Anticover of a String. CPM 2020 - 31st Annual Symposium on Combinatorial Pattern Matching, Jun 2020, Copenhagen, Denmark. pp.1-11, ⟨10.4230/LIPIcs.CPM.2020.2⟩. ⟨hal-02957658⟩

Collections

INRIA INRIA2
66 Consultations
189 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More