An information-theoretic lower bound for the longest common subsequence problem

DOI10.1016/0020-0190(78)90037-6zbMath0365.94025OpenAlexW2093513138MaRDI QIDQ1241422

Daniel S. Hirschberg

Publication date: 1978

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1911/19954

Mathematics Subject Classification ID

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

Related Items (11)

Performance analysis of some simple heuristics for computing longest common subsequences ⋮ New tabulation and sparse dynamic programming based techniques for sequence similarity problems ⋮ An \(O(ND)\) difference algorithm and its variations ⋮ Searching subsequences ⋮ A lower bound for the edit-distance problem under an arbitrary cost function ⋮ Longest common subsequences ⋮ Matching for run-length encoded strings ⋮ A systolic array for the longest common subsequence problem ⋮ APPLICATION-SPECIFIC ARRAY PROCESSORS FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM OF THREE SEQUENCES ∗ † ⋮ A fast and practical bit-vector algorithm for the longest common subsequence problem ⋮ New algorithms for the LCS problem

Cites Work

• A linear space algorithm for computing maximal common subsequences
• 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

This page was built for publication: An information-theoretic lower bound for the longest common subsequence problem