Title :
A coarse-grained multicomputer algorithm for the longest common subsequence problem
Author :
Garcia, Thierry ; Myoupo, Jean-Frédéric ; Semé, David
Author_Institution :
Lab. de Recherche en Informatique d´´Amiens, Univ. de Picardie Jules Verne, Amiens, France
Abstract :
The paper presents a coarse-grained multicomputer algorithm that solves the Longest Common Subsequence Problem. This algorithm can be implemented in the CGM with P processors in O(N/sup 2//P) in time and O(P) communication steps. It is the first CGM algorithm for this problem. We present also experimental results showing that the CGM algorithm is very efficient.
Keywords :
computational complexity; parallel algorithms; sequences; coarse-grained multicomputer algorithm; communication steps; longest common subsequence problem; processors; time; Algorithm design and analysis; Computational modeling; Computer architecture; Data compression; Error correction; Genetic engineering; Parallel processing; Pattern recognition; Phase change random access memory; User-generated content;
Conference_Titel :
Parallel, Distributed and Network-Based Processing, 2003. Proceedings. Eleventh Euromicro Conference on
Conference_Location :
Genova, Italy
Print_ISBN :
0-7695-1875-3
DOI :
10.1109/EMPDP.2003.1183610
