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

J. Y. Guo; F. K. Hwang

doi:10.1016/j.ipl.2005.01.002

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

J. Y. Guo^*, F. K. Hwang

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

8 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 language	English
Pages (from-to)	131-135
Number of pages	5
Journal	Information Processing Letters
Volume	94
Issue number	3
DOIs	https://doi.org/10.1016/j.ipl.2005.01.002
Publication status	Published - 2005 May 16
Externally published	Yes

Keywords

Algorithms
Longest common subsequence
Primal-dual algorithm

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/j.ipl.2005.01.002

Cite this

@article{d6606607d6814bb2890d325fac39e290,

title = "An almost-linear time and linear space algorithm for the longest common subsequence problem",

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.",

keywords = "Algorithms, Longest common subsequence, Primal-dual algorithm",

author = "Guo, {J. Y.} and Hwang, {F. K.}",

note = "Funding Information: ✩ Research partially supported by ROC National Science council grant NSC 90-2115-M-009-007. * Corresponding author. E-mail address: [email protected] (J.Y. Guo).",

year = "2005",

month = may,

day = "16",

doi = "10.1016/j.ipl.2005.01.002",

language = "English",

volume = "94",

pages = "131--135",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

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

AU - Guo, J. Y.

AU - Hwang, F. K.

N1 - Funding Information: ✩ Research partially supported by ROC National Science council grant NSC 90-2115-M-009-007. * Corresponding author. E-mail address: [email protected] (J.Y. Guo).

PY - 2005/5/16

Y1 - 2005/5/16

N2 - 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.

AB - 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.

KW - Algorithms

KW - Longest common subsequence

KW - Primal-dual algorithm

UR - http://www.scopus.com/inward/record.url?scp=15344344374&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=15344344374&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2005.01.002

DO - 10.1016/j.ipl.2005.01.002

M3 - Article

AN - SCOPUS:15344344374

SN - 0020-0190

VL - 94

SP - 131

EP - 135

JO - Information Processing Letters

JF - Information Processing Letters

IS - 3

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this