Hardness of longest common subsequence for sequences with bounded run-lengths - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2012

Hardness of longest common subsequence for sequences with bounded run-lengths

Résumé

The longest common subsequence (LCS) problem is a classic and well-studied problem in computer science with extensive applications in diverse areas ranging from spelling error corrections to molecular biology. This paper focuses on LCS for fixed alphabet size and fixed run-lengths (i.e., maximum number of consecutive occurrences of the same symbol). We show that LCS is NP-complete even when restricted to (i) alphabets of size 3 and run-length at most 1, and (ii) alphabets of size 2 and run-length at most 2 (both results are tight). For the latter case, we show that the problem is approximable within ratio 3/5.
Fichier principal
Vignette du fichier
hal.pdf (350.17 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00683311 , version 1 (28-03-2012)

Identifiants

Citer

Guillaume Blin, Laurent Bulteau, Minghui Jiang, Pedro J. Tejada, Stéphane Vialette. Hardness of longest common subsequence for sequences with bounded run-lengths. 23rd Annual Symposium on Combinatorial Pattern Matching (CPM'12), Jul 2012, Helsinki, Finland. pp.138-148, ⟨10.1007/978-3-642-31265-6_11⟩. ⟨hal-00683311⟩
330 Consultations
4675 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More