Time-Efficient Parallel Algorithms for the Longest Common Subsequence and Related Problems

Authors: Myoupo J-F.; Semé D.

Source: Journal of Parallel and Distributed Computing, Volume 57, Number 2, May 1999 , pp. 212-223(12)

Buy & download fulltext article:

Price: $52.63 plus tax (Refund Policy)

Abstract:

Recently Akl et al. introduced a new model of parallel computation, called broadcasting with selective reduction (BSR), and showed that it is more powerful than any CRCW PRAM and yet requires no more resources for implementation than even EREW PRAM. The model allows constant time solutions to sorting, parallel prefix, and other problems. In this paper, we describe constant time solutions to the longest common subsequence problem and the sequence alignment problem using the BSR model. These are the first constant time solutions to these problems for any model of computation. Copyright 1999 Academic Press.

Language: English

Document Type: Research article

Affiliations: Université de Picardie Jules Verne, 33, rue Saint-Leu, Amiens Cedex, 80039, France

Publication date: 1999-05-01