String factorisations with maximum or minimum dimension

12/20/2019
by   Angelo Monti, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset