Repetition-free longest common subsequence

DOI10.1016/j.dam.2009.04.023zbMath1226.05002OpenAlexW2053419093MaRDI 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 algorithmsAPX-hardnesslongest common subsequence

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Approximation algorithms (68W25)

Related Items

Repetition-free longest common subsequence of random sequences, Solving longest common subsequence problems via a transformation to the maximum clique problem, The constrained shortest common supersequence problem, On the parameterized complexity of the repetition free longest common subsequence problem, Exact algorithms for the repetition-bounded longest common subsequence problem, Doubly-constrained LCS and hybrid-constrained LCS problems revisited, A hybrid genetic algorithm for the repetition free 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

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