deposit_your_work

An Information Theoretic Lower Bound for the Longest Common Subsequence Problem

Files in this item

Files Size Format View
Hir1977Apr9AnInforma.PDF 165.5Kb application/pdf Thumbnail

Show full item record

Item Metadata

Title: An Information Theoretic Lower Bound for the Longest Common Subsequence Problem
Author: Hirschberg, D.S.
Type: Tech Report
Keywords: sequence
Citation: D. Hirschberg, "An Information Theoretic Lower Bound for the Longest Common Subsequence Problem," Rice University ECE Technical Report, no. 7705, 1977.
Abstract: We shall derive a lower on the number of "less-than-equal-greater than" comparisons required to solve the longest common subsequence (LCS) problem.
Date Published: 1977-04-20

This item appears in the following Collection(s)

  • ECE Publications [1046 items]
    Publications by Rice University Electrical and Computer Engineering faculty and graduate students