Algorithms for computing variants of the longest common subsequence problem

DOI10.1016/j.tcs.2008.01.009zbMath1142.68068OpenAlexW2091822872MaRDI QIDQ932321

M. Sohel Rahman, Costas S. Iliopoulos

Publication date: 10 July 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.01.009

zbMATH Keywords

algorithmstringslongest common subsequence

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Related Items (7)

Palindromic subsequence automata and longest common palindromic subsequence ⋮ Constrained pairwise and center-star sequences alignment problems ⋮ Computing the longest common almost-increasing subsequence ⋮ The generalized definitions of the two-dimensional largest common substructure problems ⋮ Hardness and approximation of multiple sequence alignment with column score ⋮ Finding the gapped longest common subsequence by incremental suffix maximum queries ⋮ A new efficient algorithm for computing the longest common subsequence

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
• Preserving order in a forest in less than logarithmic time and linear space
• The longest common subsequence problem for sequences with nested arc annotations.
• A fast algorithm for computing longest common subsequences
• The Complexity of Some Problems on Subsequences and Supersequences
• Algorithms for the Longest Common Subsequence Problem
• Algorithms on Strings, Trees and Sequences
• The String-to-String Correction Problem
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• Transposition invariant string matching
• Computational Science – ICCS 2005
• Combinatorial Pattern Matching
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
• Computing and Combinatorics
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Algorithms for computing variants of the longest common subsequence problem