Bounds on the Complexity of the Longest Common Subsequence Problem

Cited In (47)

Tight conditional lower bounds for longest common increasing subsequence
An overview on XML similarity: background, current trends and future directions
Communication-Efficient Private Protocols for Longest Common Subsequence
Constrained string editing
A lower bound for the edit-distance problem under an arbitrary cost function
LCS Approximation via Embedding into Local Non-repetitive Strings
A survey on tree edit distance and related problems
The shortest common supersequence problem over binary alphabet is NP- complete
Semi-local longest common subsequences in subquadratic time
Longest common subsequences
Improving the worst-case performance of the Hunt-Szymanski strategy for the longest common subsequence of two strings
The longest common subsequence problem revisited
Fast linear-space computations of longest common subsequences
Quadratic-time algorithm for a string constrained LCS problem
Resequencing a set of strings based on a target string
On the generalized constrained longest common subsequence problems
The tree-to-tree editing problem
Dynamic programming with convexity, concavity and sparsity
LCS approximation via embedding into locally non-repetitive strings
Mining Bit-Parallel LCS-length Algorithms
A systolic array for the longest common subsequence problem
A hybrid dynamic programming and memetic algorithm to the traveling salesman problem with hotel selection
Some limit results for longest common subsequences
A faster algorithm computing string edit distances
An $O(ND)$ difference algorithm and its variations
Behandlung verschiedener INTEGER-Darstellungen durch optimierende Compiler
A Linear-Time n ^0.4 -Approximation for Longest Common Subsequence
Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier
Matching for run-length encoded strings
A common basis for similarity measures involving two strings†
Title not available (Why is that?)
Performance analysis of some simple heuristics for computing longest common subsequences
A fast and practical bit-vector algorithm for the longest common subsequence problem
New algorithms for the LCS problem
An efficient algorithm for LCS problem between two arbitrary sequences
An information-theoretic lower bound for the longest common subsequence problem
On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
A bit-string longest-common-subsequence algorithm
Computing a longest common subsequence for a set of strings
Constrained LCS: Hardness and Approximation
Searching subsequences
FACC: a novel finite automaton based on cloud computing for the multiple longest common subsequences search
On finding a longest common palindromic subsequence
A fast algorithm for the longest-common-subsequence problem
Title not available (Why is that?)
DERIVING A FAST SYSTOLIC ALGORITHM FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM
Constrained sequence analysis algorithms in computational biology

This page was built for publication: Bounds on the Complexity of the Longest Common Subsequence Problem

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