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 F-Min-D problem) or the maximum (the F-Max-D problem) number of different factors. The F-Min-D 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 F-Max-D 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) and an FPT algorithm w.r.t. parameter max⁡{k,|Σ|}.

String factorisations with maximum or minimum dimension / Monti, A.; Sinaimeri, Blerina. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 842:(2020), pp. 65-73. [10.1016/j.tcs.2020.07.029]

String factorisations with maximum or minimum dimension

Sinaimeri B.
2020

Abstract

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 F-Min-D problem) or the maximum (the F-Max-D problem) number of different factors. The F-Min-D 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 F-Max-D 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) and an FPT algorithm w.r.t. parameter max⁡{k,|Σ|}.
2020
Approximation algorithms; NP-hard problems; String factorisation
String factorisations with maximum or minimum dimension / Monti, A.; Sinaimeri, Blerina. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 842:(2020), pp. 65-73. [10.1016/j.tcs.2020.07.029]
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0304397520304102-main.pdf

Solo gestori archivio

Tipologia: Documento in Post-print
Licenza: DRM (Digital rights management) non definiti
Dimensione 588.02 kB
Formato Adobe PDF
588.02 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11385/202465
Citazioni
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
  • OpenAlex ND
social impact