Back to Search
Start Over
String factorisations with maximum or minimum dimension.
- Source :
-
Theoretical Computer Science . Nov2020, Vol. 842, p65-73. 9p. - Publication Year :
- 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 , | Σ | }. [ABSTRACT FROM AUTHOR]
- Subjects :
- *MAXIMA & minima
*ALGORITHMS
*NP-hard problems
*INTEGERS
Subjects
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 842
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 146169524
- Full Text :
- https://doi.org/10.1016/j.tcs.2020.07.029