String factorisations with maximum or minimum dimension
| Autor: | Blerina Sinaimeri, Angelo Monti |
|---|---|
| Přispěvatelé: | Department of Informatics and System Sciences (Sapienza University of Rome), Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome] (UNIROMA), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Baobab, Département PEGASE [LBBE] (PEGASE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome] |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
General Computer Science Dimension (graph theory) NP-hard problems 0102 computer and information sciences Computational Complexity (cs.CC) 01 natural sciences Theoretical Computer Science Combinatorics 03 medical and health sciences Integer Factorization Computer Science - Data Structures and Algorithms Data Structures and Algorithms (cs.DS) [INFO]Computer Science [cs] Approximation algorithms String factorisation 030304 developmental biology Mathematics 0303 health sciences String (computer science) Approximation algorithm Computer Science - Computational Complexity 010201 computation theory & mathematics Bounded function |
| Zdroj: | Theoretical Computer Science Theoretical Computer Science, 2020, 842, pp.65-73. ⟨10.1016/j.tcs.2020.07.029⟩ Theoretical Computer Science, Elsevier, 2020, 842, pp.65-73. ⟨10.1016/j.tcs.2020.07.029⟩ |
| ISSN: | 1879-2294 0304-3975 |
| DOI: | 10.1016/j.tcs.2020.07.029⟩ |
| Popis: | 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 , | Σ | } . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect