An almost-linear time and linear space algorithm for the longest common subsequence problem
| dc.citation.epage | 135 | en_US |
| dc.citation.issue | 3 | en_US |
| dc.citation.spage | 131 | en_US |
| dc.citation.volume | 94 | en_US |
| dc.citation.woscount | 4 | |
| dc.contributor.author | Guo, JY | en_US |
| dc.contributor.author | Hwang, FK | en_US |
| dc.contributor.department | 應用數學系 | zh_TW |
| dc.contributor.department | Department of Applied Mathematics | en_US |
| dc.date.accessioned | 2014-12-08T15:19:08Z | |
| dc.date.available | 2014-12-08T15:19:08Z | |
| dc.date.issued | 2005-05-16 | en_US |
| dc.description.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. (c) 2005 Elsevier B.V. All rights reserved. | en_US |
| dc.identifier.doi | 10.1016/j.ipl.2005.01.002 | en_US |
| dc.identifier.issn | 0020-0190 | en_US |
| dc.identifier.journal | INFORMATION PROCESSING LETTERS | en_US |
| dc.identifier.uri | http://dx.doi.org/10.1016/j.ipl.2005.01.002 | en_US |
| dc.identifier.uri | https://ir.lib.nycu.edu.tw/handle/11536/13707 | |
| dc.identifier.wosnumber | WOS:000228458200006 | |
| dc.language.iso | en_US | en_US |
| dc.subject | algorithms | en_US |
| dc.subject | primal-dual algorithm | en_US |
| dc.subject | longest common subsequence | en_US |
| dc.title | An almost-linear time and linear space algorithm for the longest common subsequence problem | en_US |
| dc.type | Article | en_US |