LCS approximation via embedding into locally non-repetitive strings

DOI10.1016/j.ic.2010.12.006zbMath1215.68281MaRDI QIDQ716327

Ilan Newman, Gad M. Landau, Avivit Levy

Publication date: 28 April 2011

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2010.12.006

zbMATH Keywords

embedding; string algorithms; LCS approximation

Mathematics Subject Classification ID

68W25: Approximation algorithms

68W32: Algorithms on strings

Related Items

LCS\(k\): a refined similarity measure, A space efficient algorithm for the longest common subsequence in \(k\)-length substrings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sparse LCS common substring alignment
• The longest common subsequence problem revisited
• Fast string matching with k differences
• A faster algorithm computing string edit distances
• On the Common Substring Alignment Problem
• Approximate String Matching with Address Bit Errors
• Oblivious string embeddings and edit distance approximations
• Efficient randomized pattern-matching algorithms
• Bounds on the Complexity of the Longest Common Subsequence Problem
• A fast algorithm for computing longest common subsequences
• Algorithms for the Longest Common Subsequence Problem
• Algorithms on Strings, Trees and Sequences
• The String-to-String Correction Problem
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
• Approximating edit distance in near-linear time
• Matching Sequences under Deletion/Insertion Constraints
• Low distortion embeddings for edit distance