| Texto completo | |
| Autor(es): |
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.
Número total de Autores: 9
|
| Tipo de documento: | Artigo Científico |
| Fonte: | DISCRETE APPLIED MATHEMATICS; v. 158, n. 12, p. 1315-1324, 2010. |
| Resumo | |
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) | |
| Processo FAPESP: | 03/09925-5 - Fundamentos da ciência da computação: algoritmos combinatórios e estruturas discretas |
| Beneficiário: | Yoshiharu Kohayakawa |
| Modalidade de apoio: | Auxílio à Pesquisa - Programa PRONEX - Temático |
| Processo FAPESP: | 04/14335-5 - Questões algoritmicas em biologia molecular |
| Beneficiário: | Carlos Eduardo Ferreira |
| Modalidade de apoio: | Auxílio à Pesquisa - Regular |