Bounds on the Number of Longest Common Subsequences

Details Bounds on the Number of Longest Common Subsequences Bounds on the Number of Longest Common Subsequences

2003-01-28

arxiv.org/abs/cs/0301030v2

Computer Science

Discrete Mathematics

13 pages. Corrected typos, corrected operation of hyperlinks, improved presentation

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Bounds on the Number of Longest Common Subsequences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bounds on the Number of Longest Common Subsequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounds on the Number of Longest Common Subsequences will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-317132