LCS Approximation via Embedding into Local Non-repetitive Strings

DOI10.1007/978-3-642-02441-2_9MaRDI QIDQ3637107zbMATH OpenOpenAlexFDO

Authors Gad M. Landau, Ilan Newman, Avivit Levy

Publication date 7 July 2009

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02441-2_9

Mathematics Subject Classification ID

Approximation algorithms (68W25) Algorithms on strings (68W32)

Recommendations

• LCS approximation via embedding into locally non-repetitive strings
• Approximating LCS in Linear Time: Beating the √n Barrier
• Approximating longest common subsequence in linear time: beating the \(\sqrt{n}\) barrier
• A fast longest common subsequence algorithm for similar strings
• Constrained LCS: Hardness and Approximation

Cites work

• A fast algorithm for computing longest common subsequences
• A faster algorithm computing string edit distances
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• Algorithms for the Longest Common Subsequence Problem
• Algorithms on Strings, Trees and Sequences
• Approximate String Matching with Address Bit Errors
• Bounds on the Complexity of the Longest Common Subsequence Problem
• Efficient randomized pattern-matching algorithms
• Embedding the Ulam metric into \(\ell_{1}\)
• Fast string matching with k differences
• scientific article; zbMATH DE number 3551946 (Why is no real title available?)
• scientific article; zbMATH DE number 1305083 (Why is no real title available?)
• Low distortion embeddings for edit distance
• Matching Sequences under Deletion/Insertion Constraints
• Oblivious string embeddings and edit distance approximations
• On the common substring alignment problem
• Sparse LCS common substring alignment
• The computational hardness of estimating edit distance
• The longest common subsequence problem revisited
• The String-to-String Correction Problem

Cited in

(3)

• Avoiding approximate repetitions with respect to the longest common subsequence distance
• A multiobjective optimization algorithm for the weighted LCS
• LCS approximation via embedding into locally non-repetitive strings

This page was built for publication: LCS Approximation via Embedding into Local Non-repetitive Strings

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