Skip to Main content Skip to Navigation
New interface
Journal articles

String factorisations with maximum or minimum dimension

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 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download
Contributor : Marie-France Sagot Connect in order to contact the contributor
Submitted on : Friday, October 2, 2020 - 10:23:43 AM
Last modification on : Friday, November 25, 2022 - 7:04:09 PM
Long-term archiving on: : Monday, January 4, 2021 - 8:43:25 AM


Files produced by the author(s)




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⟩



Record views


Files downloads