An optimal algorithm for the longest common subsequence problem Conference Paper uri icon

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

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