In this contribution we consider Max-LL-DUP, an optimization problem that asks for a letter-duplicated subsequence of an input string that contains the maximum number of letters of the alphabet over which the input string is defined. When each letter has at most four occurrences in the input string, we prove that the problem is APX-hard. Then, we give a linear-time algorithm when each letter has at most three occurrences in the input string.
(2024). Maximum Letter-Duplicated Subsequence (short paper) . Retrieved from https://hdl.handle.net/10446/296087
Maximum Letter-Duplicated Subsequence (short paper)
Dondi, Riccardo;Hosseinzadeh, Mehdi;
2024-01-01
Abstract
In this contribution we consider Max-LL-DUP, an optimization problem that asks for a letter-duplicated subsequence of an input string that contains the maximum number of letters of the alphabet over which the input string is defined. When each letter has at most four occurrences in the input string, we prove that the problem is APX-hard. Then, we give a linear-time algorithm when each letter has at most three occurrences in the input string.File allegato/i alla scheda:
| File | Dimensione del file | Formato | |
|---|---|---|---|
|
ICTCS2024.pdf
accesso aperto
Versione:
publisher's version - versione editoriale
Licenza:
Creative commons
Dimensione del file
1.08 MB
Formato
Adobe PDF
|
1.08 MB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo
