An almost-linear time and linear space algorithm for the longest common subsequence problem

J. Y. Guo, F. K. Hwang

Research output: Contribution to journalArticle

7 Citations (Scopus)

Abstract

There are two general approaches to the longest common subsequence problem. The dynamic programming approach takes quadratic time but linear space, while the nondynamic-programming approach takes less time but more space. We propose a new implementation of the latter approach which seems to get the best for both time and space for the DNA application.

Original languageEnglish
Pages (from-to)131-135
Number of pages5
JournalInformation Processing Letters
Volume94
Issue number3
DOIs
Publication statusPublished - 2005 May 16

    Fingerprint

Keywords

  • Algorithms
  • Longest common subsequence
  • Primal-dual algorithm

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Cite this