ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS

DOI10.1142/S0129054105003674zbMath1101.68602OpenAlexW2088055539MaRDI 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 programmingedit distancelongest common subsequenceconstrained subsequence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (23)

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

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

This page was built for publication: ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS