Skip to Main content Skip to Navigation
Journal articles

On the Parameterized Complexity of the Repetition Free Longest Common Subsequence Problem

Abstract : Longest common subsequence is a widely used measure to compare strings, in particular in Computational Biology. Recently, several variants of the longest common subsequence have been introduced to tackle with the comparison of genomes. In particular, the Repetition Free Longest Common Subsequence problem (RFLCS) is a variant of the LCS problem that asks for a longest common subsequence problem of two input strings with no repetition of symbols. In this paper, we investigate the parameterized complexity of RFLCS. First, we show that the problem does not admit a polynomial kernel. Then, we present an FPT algorithm for the RFLCS problem, improving the time complexity of the existent FPT algorithm.
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00637255
Contributor : Guillaume Blin <>
Submitted on : Thursday, December 22, 2011 - 10:19:36 AM
Last modification on : Wednesday, February 26, 2020 - 7:06:06 PM
Long-term archiving on: : Thursday, March 30, 2017 - 9:08:19 PM

File

ExemplarLCS-par.pdf
Files produced by the author(s)

Identifiers

Citation

Guillaume Blin, Paola Bonizzoni, Riccardo Dondi, Florian Sikora. On the Parameterized Complexity of the Repetition Free Longest Common Subsequence Problem. Information Processing Letters, Elsevier, 2012, 112 (7), pp.272-276. ⟨10.1016/j.ipl.2011.12.009⟩. ⟨hal-00637255v2⟩

Share

Metrics

Record views

542

Files downloads

631