ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS

DOI10.1142/S0129054105003674zbMath1101.68602MaRDI QIDQ5714657

Abdullah N. Arslan, Ömer Eğecioğlu

Publication date: 15 December 2005

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054105003674

zbMATH Keywords

dynamic programming; edit distance; longest common subsequence; constrained subsequence

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

Related Items

Unnamed Item, Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier, AN ALGORITHM AND APPLICATIONS TO SEQUENCE ALIGNMENT WITH WEIGHTED CONSTRAINTS, The constrained shortest common supersequence problem, Fast algorithms for computing the constrained LCS of run-length encoded strings, Approximability of constrained LCS, Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion, On the generalized constrained longest common subsequence problems, Constrained sequence analysis algorithms in computational biology, 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, New efficient algorithms for the LCS and constrained LCS problems, Finite automata based algorithms on subsequences and supersequences of degenerate strings, An \(A^\ast\) search algorithm for the constrained longest common subsequence problem, Tight conditional lower bounds for longest common increasing subsequence, Comparing incomplete sequences via longest common subsequence, The substring inclusion constraint longest common subsequence problem can be solved in quadratic time, An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints, Fast Algorithms for Local Similarity Queries in Two Sequences, Regular Language Constrained Sequence Alignment Revisited, The Constrained Longest Common Subsequence Problem for Degenerate Strings, Constrained LCS: Hardness and Approximation

Cites Work

• The constrained longest common subsequence problem
• A faster algorithm computing string edit distances
• A simple algorithm for the constrained sequence problems
• A linear space algorithm for computing maximal common subsequences
• Algorithms for the Longest Common Subsequence Problem
• The String-to-String Correction Problem