Skip to Main content Skip to Navigation
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 metadatas

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-02955643
Contributor : Marie-France Sagot <>
Submitted on : Friday, October 2, 2020 - 10:23:43 AM
Last modification on : Wednesday, October 14, 2020 - 3:51:08 AM

File

1912.10140.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Angelo Monti, Blerina Sinaimeri. String factorisations with maximum or minimum dimension. Theoretical Computer Science, Elsevier, 2020, 842, pp.65-73. ⟨10.1016/j.tcs.2020.07.029⟩. ⟨hal-02955643⟩

Share

Metrics

Record views

32

Files downloads

99