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

DOI10.1016/0020-0190(78)90037-6MaRDI QIDQ1241422zbMATH OpenOpenAlexFDO

Authors 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

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

Cites work

• A fast algorithm for computing longest common subsequences
• A linear space algorithm for computing maximal common subsequences
• Algorithms for the Longest Common Subsequence Problem
• Bounds on the Complexity of the Longest Common Subsequence Problem

Cited in

(11)

• 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
• New tabulation and sparse dynamic programming based techniques for sequence similarity problems
• APPLICATION-SPECIFIC ARRAY PROCESSORS FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM OF THREE SEQUENCES ∗ †
• Longest common subsequences

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

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