APPLICATION-SPECIFIC ARRAY PROCESSORS FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM OF THREE SEQUENCES *†
作者:
GUILLAUME LUCE,
JEAN FRÉDÉRIC MYOUPO,
期刊:
Parallel Algorithms and Applications
(Taylor Available online 1998)
卷期:
Volume 13,
issue 1
页码: 27-52
ISSN:1063-7192
年代: 1998
DOI:10.1080/01495739808947359
出版商: Taylor & Francis Group
关键词: Systolic-based parallel architectures and algorithms;VLSI systems;Special purpose processors;Longest common subsequence problem of three strings;Dynamic programming
数据来源: Taylor
摘要:
We design linear time systolic-based parallel algorithms that run on two-dimensional arrays for both computing the length and recovering a longest common subsequence of three given sequences that are appropriate for very large-scale integration (VLSI) implementation. These problems have been qualified to be difficult to be solved in linear time in [14], and our approach, which generalizes the methods used for determining a longest common subsequence of two strings [28,38] to the case of three strings, enables to solve both problems in linear time. Given the three sequences A, B and C of length n, m and l (n ≤ m ≤ l;), we provide an algorithm that computes the length p of their longest common subsequence on a modular I/O bounded one-way two-dimensional array of nm processors in n + 2m + l− 1 time-steps. To compute a longest common subsequence of the three given strings, we show that each processor of the above array requires an O(min{n,p\) local storage to solve the problem in In + 1m + 1 + p — 2 time-steps.
点击下载:
PDF (634KB)
返 回