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

DOI10.1016/0020-0190(78)90037-6zbMath0365.94025MaRDI 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

68Q25: Analysis of algorithms and problem complexity

94A15: Information theory (general)

68N01: General topics in the theory of software

68W99: Algorithms in computer science

Related Items

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

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