Exact algorithms for the repetition-bounded longest common subsequence problem

DOI10.1016/j.tcs.2020.07.042zbMath1453.68226OpenAlexW3047376977MaRDI QIDQ2197547

Yuichi Asahiro, Eiji Miyano, Tadatoshi Utashima, Hirotaka Ono, Jesper Jansson, Guo-Hui Lin

Publication date: 1 September 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2020.07.042

zbMATH Keywords

dynamic programmingNP-hardnessAPX-hardnessrepetition-freenessexponential-time exact algorithmsrepetition-bounded longest common subsequence problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Repetition-free longest common subsequence of random sequences
• Variants of constrained longest common subsequence
• On the parameterized complexity of the repetition free longest common subsequence problem
• The string merging problem
• A hybrid genetic algorithm for the repetition free longest common subsequence problem
• A linear space algorithm for computing maximal common subsequences
• The Complexity of Some Problems on Subsequences and Supersequences
• Algorithms for the Longest Common Subsequence Problem
• The String-to-String Correction Problem
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• Spelling correction in systems programs
• Matching Sequences under Deletion/Insertion Constraints
• Repetition-free longest common subsequence
• Better heuristic algorithms for the repetition free LCS and other variants