Parallel algorithms for the longest common subsequence problem
Academic Article

 Overview

 Research

 Identity

 Additional Document Info

 View All

Overview
abstract

A subsequence of a given string is any string obtained by deleting none or some symbols from the given string. A longest common subsequence of two strings is a common subsequence of both that is as long as any other common subsequences. The longest common subsequence problem is to find the longest common subsequence of two given strings. The bound on the complexity of this problem under the decision tree model is known as mn if the number of distinct symbols that can appear in strings is infinite, where m and n are the lengths of the two strings, respectively, and m < n. In this paper, we propose two parallel algorithms for this problem on the CREWPRAM model. One takes 0(log2rn + log n) time with mn/ log m processors, which is faster than all the existing algorithms on the same model. The other takes O(log2m log log m) time with mn/log2 m log log m processors when log2 m log log m > logn, or otherwise O(logn) time with mn/ log n processors, which is optimal in the sense that the time x processors bound matches the complexity bound of the problem. Both algorithms exploit nice properties of the LCS problem that are discovered in this paper. © 1994 IEEE
author list (cited authors)
citation count
publication date
publisher
published in
Research
keywords

Concurrent Readexclusive Writeparallel Randomaccess Machine (crewpram)

Grid Directed Graph

Longest Common Subsequence

Maximumcost Path

Parallel Algorithm

Totally Monotone Array
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume
issue