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

DOI10.1016/J.TCS.2012.01.038MaRDI QIDQ428842zbMATH OpenOpenAlexFDO

Authors Hsing-Yen Ann, Chang-Biau Yang, Chiou-Ting Tseng, 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

longest common subsequencedesign of algorithmsrun-length encodingconstrained LCS

Mathematics Subject Classification ID

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

Recommendations

• Faster STR-IC-LCS computation via RLE
• 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
• A fast algorithm of constrained longest common subsequence
• scientific article; zbMATH DE number 6697960

Cites work

• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• A fast algorithm for computing longest common subsequences
• A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings
• A simple algorithm for the constrained sequence problems
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
• Algorithms for the Longest Common Subsequence Problem
• An algorithm and applications to sequence alignment with weighted constraints
• An improved algorithm for computing the edit distance of run-length coded strings
• Beam search for the longest common subsequence problem
• Finding a longest common subsequence between a run-length-encoded string and an uncompressed string
• Finding the longest common subsequence for multiple biological sequences by ant colony optimization
• Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism
• Matching for run-length encoded strings
• New efficient algorithms for the LCS and constrained LCS problems
• On the generalized constrained longest common subsequence problems
• Preserving order in a forest in less than logarithmic time and linear space
• Regular expression constrained sequence alignment
• The Complexity of Some Problems on Subsequences and Supersequences
• The String-to-String Correction Problem
• The constrained longest common subsequence problem

Cited in

(13)

• Lyndon factorization algorithms for small alphabets and run-length encoded strings
• New efficient algorithms for the LCS and constrained LCS problems
• An efficient algorithm for the longest common palindromic subsequence problem
• Linear-space S-table algorithms for the longest common subsequence problem
• A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings
• Fast algorithms for the shortest unique palindromic substring problem on run-length encoded strings
• Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism
• On computing average common substring over run length encoded sequences
• A faster algorithm for the computation of string convolutions using LZ78 parsing
• Near-optimal computation of runs over general alphabet via non-crossing LCE queries
• Finding a longest common subsequence between a run-length-encoded string and an uncompressed string
• Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion
• Faster STR-IC-LCS computation via RLE

This page was built for publication: Fast algorithms for computing the constrained LCS of run-length encoded strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q428842)