@Article{blin12parameterized,
  author    = {Blin, Guillaume and Bonizzoni, Paola and Dondi, Riccardo and Sikora, Florian},
  title     = {On the Parameterized Complexity of the Repetition Free Longest Common Subsequence Problem},
  journal   = IPL,
  year      = {2012},
  volume    = {112},
  number    = {7},
  pages     = {272--276},
  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 the comparison of genomes. In particular, the Repetition Free Longest Common Subsequence (RFLCS) problem is a variant of the LCS problem that asks for a longest common subsequence 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 a randomized FPT algorithm for the RFLCS problem, improving the time complexity of the existent FPT algorithm.},
  doi       = {10.1016/j.ipl.2011.12.009},
  keywords  = {fpt; jena; PABI},
  owner     = {florian},
  timestamp = {2011.12.20},
  url       = {http://hal-univ-mlv.archives-ouvertes.fr/hal-00637255/en},
}

{"_id":"ZQKtHstEmoTzCxkGt","bibbaseid":"blin-bonizzoni-dondi-sikora-ontheparameterizedcomplexityoftherepetitionfreelongestcommonsubsequenceproblem-2012","authorIDs":[],"author_short":["Blin, G.","Bonizzoni, P.","Dondi, R.","Sikora, F."],"bibdata":{"bibtype":"article","type":"article","author":[{"propositions":[],"lastnames":["Blin"],"firstnames":["Guillaume"],"suffixes":[]},{"propositions":[],"lastnames":["Bonizzoni"],"firstnames":["Paola"],"suffixes":[]},{"propositions":[],"lastnames":["Dondi"],"firstnames":["Riccardo"],"suffixes":[]},{"propositions":[],"lastnames":["Sikora"],"firstnames":["Florian"],"suffixes":[]}],"title":"On the Parameterized Complexity of the Repetition Free Longest Common Subsequence Problem","journal":"Inform Process Lett","year":"2012","volume":"112","number":"7","pages":"272–276","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 the comparison of genomes. In particular, the Repetition Free Longest Common Subsequence (RFLCS) problem is a variant of the LCS problem that asks for a longest common subsequence 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 a randomized FPT algorithm for the RFLCS problem, improving the time complexity of the existent FPT algorithm.","doi":"10.1016/j.ipl.2011.12.009","keywords":"fpt; jena; PABI","owner":"florian","timestamp":"2011.12.20","url":"http://hal-univ-mlv.archives-ouvertes.fr/hal-00637255/en","bibtex":"@Article{blin12parameterized,\n author = {Blin, Guillaume and Bonizzoni, Paola and Dondi, Riccardo and Sikora, Florian},\n title = {On the Parameterized Complexity of the Repetition Free Longest Common Subsequence Problem},\n journal = IPL,\n year = {2012},\n volume = {112},\n number = {7},\n pages = {272--276},\n 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 the comparison of genomes. In particular, the Repetition Free Longest Common Subsequence (RFLCS) problem is a variant of the LCS problem that asks for a longest common subsequence 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 a randomized FPT algorithm for the RFLCS problem, improving the time complexity of the existent FPT algorithm.},\n doi = {10.1016/j.ipl.2011.12.009},\n keywords = {fpt; jena; PABI},\n owner = {florian},\n timestamp = {2011.12.20},\n url = {http://hal-univ-mlv.archives-ouvertes.fr/hal-00637255/en},\n}\n\n","author_short":["Blin, G.","Bonizzoni, P.","Dondi, R.","Sikora, F."],"key":"blin12parameterized","id":"blin12parameterized","bibbaseid":"blin-bonizzoni-dondi-sikora-ontheparameterizedcomplexityoftherepetitionfreelongestcommonsubsequenceproblem-2012","role":"author","urls":{"Paper":"http://hal-univ-mlv.archives-ouvertes.fr/hal-00637255/en"},"keyword":["fpt; jena; PABI"],"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"https://git.bio.informatik.uni-jena.de/fleisch/literature/raw/master/group-literature.bib","creationDate":"2019-11-19T16:29:35.096Z","downloads":0,"keywords":["fpt; jena; pabi"],"search_terms":["parameterized","complexity","repetition","free","longest","common","subsequence","problem","blin","bonizzoni","dondi","sikora"],"title":"On the Parameterized Complexity of the Repetition Free Longest Common Subsequence Problem","year":2012,"dataSources":["C5FtkvWWggFfMJTFX"]}