| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 419539 | Discrete Applied Mathematics | 2010 | 10 Pages |
Abstract
We study the following problem. Given two sequences xx and yy over a finite alphabet, find a repetition-free longest common subsequence of xx and yy. 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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Said S. Adi, Marília D.V. Braga, Cristina G. Fernandes, Carlos E. Ferreira, Fábio Viduani Martinez, Marie-France Sagot, Marco A. Stefanes, Christian Tjandraatmadja, Yoshiko Wakabayashi,