Fast algorithms for computing the constrained LCS of run-length encoded strings

DOI10.1016/j.tcs.2012.01.038zbMath1242.68384OpenAlexW2011654664MaRDI QIDQ428842

Chiou-Ting Tseng, Chang-Biau Yang, Hsing-Yen Ann, Chiou-Yi Hor

Publication date: 25 June 2012

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

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

zbMATH Keywords

design of algorithmsrun-length encodinglongest common subsequenceconstrained LCS

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Algorithms on strings (68W32)

Related Items

An efficient algorithm for the longest common palindromic subsequence problem ⋮ Linear-space S-table algorithms for the longest common subsequence problem ⋮ Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion

Cites Work

• Unnamed Item
• On the generalized constrained longest common subsequence problems
• An improved algorithm for computing the edit distance of run-length coded strings
• Beam search for the longest common subsequence problem
• Regular expression constrained sequence alignment
• Finding the longest common subsequence for multiple biological sequences by ant colony optimization
• New efficient algorithms for the LCS and constrained LCS problems
• A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings
• The constrained longest common subsequence problem
• Preserving order in a forest in less than logarithmic time and linear space
• Matching for run-length encoded strings
• Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism
• A simple algorithm for the constrained sequence problems
• Finding a longest common subsequence between a run-length-encoded string and an uncompressed string
• A fast algorithm for computing longest common subsequences
• The Complexity of Some Problems on Subsequences and Supersequences
• Algorithms for the Longest Common Subsequence Problem
• The String-to-String Correction Problem
• AN ALGORITHM AND APPLICATIONS TO SEQUENCE ALIGNMENT WITH WEIGHTED CONSTRAINTS
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS