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 (10)

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

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Repetition-free longest common subsequence