Name
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, vertical bar E vertical bar}. (C) 2020 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1016/j.tcs.2020.07.029 | THEORETICAL COMPUTER SCIENCE |
Keywords | DocType | Volume |
String factorisation,NP-hard problems,Approximation algorithms | Journal | 842 |
ISSN | Citations | PageRank |
0304-3975 | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Angelo Monti | 1 | 671 | 46.93 |
| B. Sinaimeri | 2 | 47 | 11.75 |