Bounds on the Number of Longest Common Subsequences.
Document Type
Technical Report
Publication Date
8-2003
Publication Title
Computer Science Research Repository
Abstract
This paper performs the analysis necessary to bound the running time of known, efficient algorithms for generating all longest common subsequences. That is, we bound the running time as a function of input size for algorithms with time essentially proportional to the output size. This paper considers both the case of computing all distinct LCSs and the case of computing all LCS embeddings. Also included is an analysis of how much better the efficient algorithms are than the standard method of generating LCS embeddings. A full analysis is carried out with running times measured as a function of the total number of input characters, and much of the analysis is also provided for cases in which the two input sequences are of the same specified length or of two independently specified lengths.
Identifier
arXiv:cs/0301030
Recommended Citation
Ronald I. Greenberg. Bounds on the number of longest common subsequences. Technical report, Computer Science Research Repository (http://arXiv.org), 2003. Article ID cs/0301030v2.
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.
Presentation slides from SIAM Conference on Discrete Mathematics, Nashville, TN, June 13, 2004.
Comments
© 2011 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works.