Repetition-free longest common subsequence
| Contribuinte(s) |
UNIVERSIDADE DE SÃO PAULO |
|---|---|
| Data(s) |
20/10/2012
20/10/2012
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. |
| Identificador |
DISCRETE APPLIED MATHEMATICS, v.158, n.12, Special Issue, p.1315-1324, 2010 0166-218X http://producao.usp.br/handle/BDPI/30369 10.1016/j.dam.2009.04.023 |
| Idioma(s) |
eng |
| Publicador |
ELSEVIER SCIENCE BV |
| Relação |
Discrete Applied Mathematics |
| Direitos |
restrictedAccess Copyright ELSEVIER SCIENCE BV |
| Palavras-Chave | #Longest common subsequence #APX-hardness #Approximation algorithms #Mathematics, Applied |
| Tipo |
article proceedings paper publishedVersion |
