標題: An almost-linear time and linear space algorithm for the longest common subsequence problem
作者: Guo, JY
Hwang, FK
應用數學系
Department of Applied Mathematics
關鍵字: algorithms;primal-dual algorithm;longest common subsequence
公開日期: 16-May-2005
摘要: 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. (c) 2005 Elsevier B.V. All rights reserved.
URI: http://dx.doi.org/10.1016/j.ipl.2005.01.002
http://hdl.handle.net/11536/13707
ISSN: 0020-0190
DOI: 10.1016/j.ipl.2005.01.002
期刊: INFORMATION PROCESSING LETTERS
Volume: 94
Issue: 3
起始頁: 131
結束頁: 135
Appears in Collections:Articles


Files in This Item:

  1. 000228458200006.pdf