Bounds on the Complexity of the Longest Common Subsequence Problem

DOI10.1145/321921.321922zbMath0316.68027OpenAlexW2038268267MaRDI QIDQ4077445

Jeffrey D. Ullman, A. V. Aho, Daniel S. Hirschberg

Publication date: 1976

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/321921.321922

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) General topics in the theory of software (68N01) Algorithms in computer science (68W99)

Related Items

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