Repetition-free longest common subsequence

S.S Adi , M. Braga (1) , C.G. Fernandes , C.E. Ferreira , F.V. Martinez , M.-F. Sagot (1) , M.A. Stefanes , C. Tjandraatmadja , Y. Wakabayashi

1 Baobab

We study the following problem. Given two sequences x and y over a finite alphabet, find a repetition-free longest common subsequence of x and y. We show several algorithmic results, a computational complexity result, and we describe a preliminary experimental study based on the proposed algorithms. We also show that this problem is APX-hard.

Domaines: Autre [q-bio.OT]

S.S Adi, M. Braga, C.G. Fernandes, C.E. Ferreira, F.V. Martinez, et al.. Repetition-free longest common subsequence. Discrete Applied Mathematics, 2010, 158 (12), pp.1315-1324. ⟨10.1016/j.dam.2009.04.023⟩. ⟨hal-00539257⟩