An optimal algorithm for the longest common subsequence problem Conference Paper

abstract

• 1991 IEEE. The longest common subsequence problem is to find a longest common subsequence of two given strings. The complexity of this problem on the decision tree model is known as mn, where m and n are the lengths of these two strings, respectively, and m- n. We present a parallel algorithm for this problem on the CREW PRAM model, which takes O(log2mloglogm) time with mn/log2mloglogm processors when log2mloglogmlogn, or otherwise O(1ogn) time with mnfiogn processors.

name of conference

• Proceedings of the Third IEEE Symposium on Parallel and Distributed Processing

authors

• Lu, Mi

published proceedings

• Proceedings of the Third IEEE Symposium on Parallel and Distributed Processing

author list (cited authors)

• Lin, H., Lu, M., & Fang, J.

citation count

• 4

complete list of authors

• Lin, H||Lu, M||Fang, J

publication date

• January 1991

publisher

• Institute of Electrical and Electronics Engineers (IEEE)  Publisher

Digital Object Identifier (DOI)

• 10.1109/spdp.1991.218203

International Standard Book Number (ISBN) 10

• 0818623101

International Standard Book Number (ISBN) 13

• 9780818623103

start page

• 630

end page

• 639

URL

• http://dx.doi.org/10.1109/spdp.1991.218203