| Full text | |
| Author(s): |
Adi‚ S.S.
;
Braga‚ M.D.V.
;
Fernandes‚ C.G.
;
Ferreira‚ C.E.
;
Martinez‚ F.V.
;
Sagot‚ M.F.
;
Stefanes‚ M.A.
;
Tjandraatmadja‚ C.
;
Wakabayashi‚ Y.
Total Authors: 9
|
| Document type: | Journal article |
| Source: | DISCRETE APPLIED MATHEMATICS; v. 158, n. 12, p. 1315-1324, 2010. |
| Abstract | |
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. (C) 2009 Elsevier B.V. All rights reserved. (AU) | |
| FAPESP's process: | 03/09925-5 - Foundations of computer science: combinatory algorithms and discrete structures |
| Grantee: | Yoshiharu Kohayakawa |
| Support Opportunities: | PRONEX Research - Thematic Grants |