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 -