New efficient algorithms for the LCS and constrained LCS problems

DOI10.1016/j.ipl.2007.09.008zbMath1186.68543OpenAlexW1974671004MaRDI QIDQ963324

M. Sohel Rahman, Costas S. Iliopoulos

Publication date: 19 April 2010

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

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

zbMATH Keywords

algorithmscombinatorial problemslongest common subsequence

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Related Items (19)

Palindromic subsequence automata and longest common palindromic subsequence ⋮ The substring inclusion constraint longest common subsequence problem can be solved in quadratic time ⋮ Computing the longest common almost-increasing subsequence ⋮ A hardness result and new algorithm for the longest common palindromic subsequence problem ⋮ An efficient algorithm for the longest common palindromic subsequence problem ⋮ The constrained shortest common supersequence problem ⋮ Fast algorithms for computing the constrained LCS of run-length encoded strings ⋮ Doubly-constrained LCS and hybrid-constrained LCS problems revisited ⋮ Approximability of constrained LCS ⋮ An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints ⋮ An \(A^\ast\) search algorithm for the constrained longest common subsequence problem ⋮ Regular Language Constrained Sequence Alignment Revisited ⋮ 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 ⋮ Finite automata based algorithms on subsequences and supersequences of degenerate strings ⋮ AN ALGORITHM AND APPLICATIONS TO SEQUENCE ALIGNMENT WITH WEIGHTED CONSTRAINTS ⋮ A new efficient algorithm for computing the longest common subsequence ⋮ Unnamed Item

Cites Work

• The constrained longest common subsequence problem
• An \(O(ND)\) difference algorithm and its variations
• A faster algorithm computing string edit distances
• A longest common subsequence algorithm suitable for similar text strings
• A simple algorithm for the constrained sequence problems
• A fast algorithm for computing longest common subsequences
• The Complexity of Some Problems on Subsequences and Supersequences
• The String-to-String Correction Problem
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• Faster Algorithms for Computing Longest Common Increasing Subsequences
• A New Efficient Algorithm for Computing the Longest Common Subsequence
• Algorithms for Computing Variants of the Longest Common Subsequence Problem
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: New efficient algorithms for the LCS and constrained LCS problems