|
|||||
|
|
Repetition-free longest common subsequence |
|
| Authors: | Said S Adi Cristina G Fernandes Fábio Viduani Martinez Marco A Stefanes Yoshiko Wakabayashi |
| Institution: | a Universidade Federal do Mato Grosso do Sul, Brazil b Université Claude Bernard, Lyon I, France c Universidade de São Paulo, Brazil |
| 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. |
| Keywords: | Longest common subsequence APX-hardness" target="_blank">APX-hardness Approximation algorithms |
| 本文献已被 ScienceDirect 等数据库收录！ | |