Exact algorithms for the repetition-bounded longest common subsequence problem

DOI10.1016/J.TCS.2020.07.042MaRDI QIDQ2197547zbMATH OpenOpenAlexFDO

Authors Yuichi Asahiro, Jesper Jansson, Eiji Miyano, Hirotaka Ono, Tadatoshi Utashima, Guohui 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

APX-hardnessdynamic programmingexponential-time exact algorithmsNP-hardnessrepetition-bounded longest common subsequence problemrepetition-freeness

Mathematics Subject Classification ID

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

Recommendations

• Exact algorithms for the bounded repetition longest common subsequence problem
• Better heuristic algorithms for the repetition free LCS and other variants
• Repetition-free longest common subsequence
• On the parameterized complexity of the repetition free longest common subsequence problem
• Repetition-free longest common subsequence

Cites work

• A hybrid genetic algorithm for the repetition free longest common subsequence problem
• A linear space algorithm for computing maximal common subsequences
• Algorithms for the Longest Common Subsequence Problem
• Beam-ACO for the repetition-free longest common subsequence problem
• Better heuristic algorithms for the repetition free LCS and other variants
• Construct, merge, solve and adapt: application to the repetition-free longest common subsequence problem
• scientific article; zbMATH DE number 3767009 (Why is no real title available?)
• Introduction to algorithms.
• Matching Sequences under Deletion/Insertion Constraints
• Multivariate algorithmics for NP-hard string problems
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• On the parameterized complexity of the repetition free longest common subsequence problem
• Repetition-free longest common subsequence
• Repetition-free longest common subsequence of random sequences
• Spelling correction in systems programs
• The Complexity of Some Problems on Subsequences and Supersequences
• The string merging problem
• The String-to-String Correction Problem
• Variants of constrained longest common subsequence

Cited in

(10)

• Exact algorithms for the bounded repetition longest common subsequence problem
• Exact algorithms for two integer-valued problems of searching for the largest subset and longest subsequence
• On the use of decision diagrams for finding repetition-free longest common subsequences
• On the parameterized complexity of the repetition free longest common subsequence problem
• Parameterized complexity and approximability of the longest compatible sequence problem
• String Processing and Information Retrieval
• A Polyhedral Investigation of the LCS Problem and a Repetition-Free Variant
• Repetition-free longest common subsequence
• Better heuristic algorithms for the repetition free LCS and other variants
• Polynomial-time equivalences and refined algorithms for longest common subsequence variants

This page was built for publication: Exact algorithms for the repetition-bounded longest common subsequence problem

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