Repetition-free longest common subsequence

DOI10.1016/J.ENDM.2008.01.042MaRDI QIDQ5900087zbMATH OpenOpenAlexFDO

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

Publication date 5 June 2008

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2008.01.042

zbMATH Keywords

approximation algorithmsAPX-hardlongest common subsequence

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Other combinatorial number theory (11B75) Approximation algorithms (68W25)

Recommendations

• Repetition-free longest common subsequence
• Repetition-free longest common subsequence of random sequences
• Longest common subsequences
• Avoiding approximate repetitions with respect to the longest common subsequence distance
• The longest common subsequence problem revisited
• A branch-and-cut approach to the repetition-free longest common subsequence problem
• On the parameterized complexity of the repetition free longest common subsequence problem
• Longest common subsequence in sublinear space
• Exact algorithms for the repetition-bounded longest common subsequence problem

Cites work

• Exemplar Longest Common Subsequence
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• Optimization, approximation, and complexity classes
• The complexity of calculating exemplar distances

Cited in

(11)

• Exact algorithms for the bounded repetition longest common subsequence problem
• Exact algorithms for the repetition-bounded longest common subsequence problem
• A hybrid genetic algorithm for the repetition free longest common subsequence problem
• Avoiding approximate repetitions with respect to the longest common subsequence distance
• A branch-and-cut approach to the repetition-free longest common subsequence problem
• Repetition-free longest common subsequence of random sequences
• Variants of constrained longest common subsequence
• A Polyhedral Investigation of the LCS Problem and a Repetition-Free Variant
• Repetition-free longest common subsequence
• Cyclic longest common subsequence
• Polynomial-time equivalences and refined algorithms for longest common subsequence variants

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5900087)