The constrained longest common subsequence problem

DOI10.1016/J.IPL.2003.07.001MaRDI QIDQ1029006zbMATH OpenOpenAlexFDO

Authors Yin Te Tsai

Publication date 9 July 2009

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2003.07.001

zbMATH Keywords

algorithmsconstrained longest common subsequence problemsdynamic programming

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Dynamic programming (90C39)

Recommendations

• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
• A simple algorithm for the constrained sequence problems
• On the generalized constrained longest common subsequence problems
• scientific article; zbMATH DE number 6697960
• Efficient algorithms for the longest common subsequence problem with sequential substring constraints

Cites work

• A faster algorithm computing string edit distances
• Algorithms for the Longest Common Subsequence Problem
• scientific article; zbMATH DE number 1044854 (Why is no real title available?)
• scientific article; zbMATH DE number 1047152 (Why is no real title available?)
• The Complexity of Some Problems on Subsequences and Supersequences
• The String-to-String Correction Problem

Cited in

(61)

• A simple algorithm for solving for the generalized longest common subsequence (LCS) problem with a substring exclusion constraint
• Improvised divide and conquer approach for the LIS problem
• Efficient algorithms for the longest common subsequence problem with sequential substring constraints
• A data structure for substring-substring LCS length queries
• Computing the longest common almost-increasing subsequence
• An \(A^\ast\) search algorithm for the constrained longest common subsequence problem
• Tight conditional lower bounds for longest common increasing subsequence
• Maximal common subsequence algorithms
• Comparing incomplete sequences via longest common subsequence
• Resequencing a set of strings based on a target string
• Indeterminate string factorizations and degenerate text transformations
• The substring inclusion constraint longest common subsequence problem can be solved in quadratic time
• Efficient algorithms for regular expression constrained sequence alignment
• RNA multiple structural alignment with longest common subsequences
• A simple algorithm for the constrained sequence problems
• A dynamic programming solution to a generalized LCS problem
• An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints
• A hybrid genetic algorithm for the repetition free longest common subsequence problem
• Solving longest common subsequence problems via a transformation to the maximum clique problem
• An efficient algorithm for the longest common palindromic subsequence problem
• On solving a generalized constrained longest common subsequence problem
• scientific article; zbMATH DE number 1615278 (Why is no real title available?)
• The set closest common subsequence problem
• LCSk: a refined similarity measure
• Fast Algorithms for Local Similarity Queries in Two Sequences
• scientific article; zbMATH DE number 6697960 (Why is no real title available?)
• Regular language constrained sequence alignment revisited
• A multiobjective optimization algorithm for the weighted LCS
• Faster STR-EC-LCS computation
• An algorithm for the constrained heaviest common subsequence problem
• The Constrained Longest Common Subsequence Problem for Degenerate Strings
• Constrained LCS: Hardness and Approximation
• The constrained shortest common supersequence problem
• Variants of constrained longest common subsequence
• Fast algorithms for computing the constrained LCS of run-length encoded strings
• Quadratic-time algorithm for a string constrained LCS problem
• Doubly-constrained LCS and hybrid-constrained LCS problems revisited
• Approximability of constrained LCS
• Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion
• On the generalized constrained longest common subsequence problems
• Bit-parallel algorithm for the constrained longest common subsequence problem
• The longest filled common subsequence problem
• Tight conditional lower bounds for longest common increasing subsequence
• Maximal common subsequence algorithms
• Bit-parallel algorithms for the merged longest common subsequence problem
• An algorithm and applications to sequence alignment with weighted constraints
• Constrained sequence analysis algorithms in computational biology
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
• Linear-space S-table algorithms for the longest common subsequence problem
• Space-efficient STR-IC-LCS computation
• Algorithms and hardness for the longest common subsequence of three strings and related problems
• Faster space-efficient STR-IC-LCS computation
• String editing under pattern constraints
• The generalized constrained longest common subsequence in the run-length encoded format
• Efficient algorithms for enumerating maximal common subsequences of two strings
• A new efficient algorithm for computing the longest common subsequence
• Regular expression constrained sequence alignment
• Algorithms for computing variants of the longest common subsequence problem
• Thermodynamical approach to the longest common subsequence problem
• New efficient algorithms for the LCS and constrained LCS problems
• Finite automata based algorithms on subsequences and supersequences of degenerate strings

This page was built for publication: The constrained longest common subsequence problem

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