LCS Approximation via Embedding into Local Non-repetitive Strings

DOI10.1007/978-3-642-02441-2_9zbMath1247.68337OpenAlexW1686772774MaRDI QIDQ3637107

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)

Related Items (1)

A multiobjective optimization algorithm for the weighted LCS

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
• The Computational Hardness of Estimating Edit Distance
• 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
• Matching Sequences under Deletion/Insertion Constraints
• Low distortion embeddings for edit distance

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