String factorisations with maximum or minimum dimension - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2020

String factorisations with maximum or minimum dimension

Résumé

In this paper we consider two problems concerning string factorisation. Specifically given a string w and an integer k find a factorisation of w where each factor has length bounded by k and has the minimum (the FmD problem) or the maximum (the FMD problem) number of different factors. The FmD has been proved to be NP-hard even if k = 2 in [9] and for this case we provide a 3/2-approximation algorithm. The FMD problem, up to our knowledge has not been considered in the literature. We show that this problem is NP-hard for any k ≥ 3. In view of this we propose a 2-approximation algorithm (for any k) an exact exponential algorithm. We conclude with some open problems.
Fichier principal
Vignette du fichier
1912.10140.pdf (202.64 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02955643 , version 1 (02-10-2020)

Identifiants

Citer

Angelo Monti, Blerina Sinaimeri. String factorisations with maximum or minimum dimension. Theoretical Computer Science, 2020, 842, pp.65-73. ⟨10.1016/j.tcs.2020.07.029⟩. ⟨hal-02955643⟩
46 Consultations
98 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More