Repetition-free longest common subsequence

DOI10.1016/j.dam.2009.04.023zbMath1226.05002MaRDI QIDQ5901069

Cristina G. Fernandes, Marília D. V. Braga, Carlos E. Ferreira, Marco A. Stefanes, Marie-France Sagot, Said S. Adi, Christian Tjandraatmadja, Yoshiko Wakabayashi, Fábio Viduani Martinez

Publication date: 13 August 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2009.04.023

zbMATH Keywords

approximation algorithms; APX-hardness; longest common subsequence

Mathematics Subject Classification ID

05A05: Permutations, words, matrices

68W25: Approximation algorithms

Related Items

Repetition-free longest common subsequence of random sequences, The constrained shortest common supersequence problem, On the parameterized complexity of the repetition free longest common subsequence problem, Doubly-constrained LCS and hybrid-constrained LCS problems revisited, Exact algorithms for the repetition-bounded longest common subsequence problem, An \(A^\ast\) search algorithm for the constrained longest common subsequence problem, Comparing incomplete sequences via longest common subsequence, Anytime algorithms for the longest common palindromic subsequence problem, A hybrid genetic algorithm for the repetition free longest common subsequence problem, Solving longest common subsequence problems via a transformation to the maximum clique problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization, approximation, and complexity classes
• Exemplar Longest Common Subsequence
• A Polyhedral Investigation of the LCS Problem and a Repetition-Free Variant
• Repetition-free longest common subsequence