loading...
A BSP/CGM Algorithm for the All-Substrings Longest Common Subsequence Problem
Nice, France April 22-April 26
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/IPDPS.2003.1213150International Parallel and Distribute ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
C. E. R. Alves, E. N. Cáceres, S. W. Song, "A BSP/CGM Algorithm for the All-Substrings Longest Common Subsequence Problem," Parallel and Distributed Processing Symposium, International, pp. 57a, International Parallel and Distributed Processing Symposium (IPDPS'03), 2003.
 
 
BibTex
x
 
@article{ 10.1109/IPDPS.2003.1213150,
author = {C. E. R. Alves and E. N. Cáceres and S. W. Song},
title = {A BSP/CGM Algorithm for the All-Substrings Longest Common Subsequence Problem},
journal ={Parallel and Distributed Processing Symposium, International},
volume = {0},
year = {2003},
issn = {1530-2075},
pages = {57a},
doi = {http://doi.ieeecomputersociety.org/10.1109/IPDPS.2003.1213150},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Parallel and Distributed Processing Symposium, International
TI - A BSP/CGM Algorithm for the All-Substrings Longest Common Subsequence Problem
SN - 1530-2075
SP
EP
A1 - C. E. R. Alves,
A1 - E. N. Cáceres,
A1 - S. W. Song,
PY - 2003
KW - Parallel algorithms
KW - longest common subsequence
KW - BSP
KW - CGM
KW - LCS
VL - 0
JA - Parallel and Distributed Processing Symposium, International
ER -
 
C. E. R. Alves, Universidade São Judas Tadeu
E. N. Cáceres, Universidade Federale Mato Grosso do Sul
S. W. Song, Universidade de São Paulo
Given two strings X and Y of lengths mand n, respectively, the all-substrings longest common subsequence (ALCS) problem obtains the lengths of the subsequences common to X and any substring of Y . The sequential algorithm takes O(mn) time and O(n) space. We present a parallel algorithm for ALCS on a coarse-grained multicomputer (BSP/CGM) model with p < \sqrt m processors that takes O(mn/p) time and O(n\sqrt m) space per processor, with O(log p) communication rounds. The proposed parallel algorithm also solves the well-known LCS problem. To our knowledge this is the best BSP/CGM algorithm for the ALCS problem in the literature.
Index Terms:
Parallel algorithms, longest common subsequence, BSP, CGM, LCS
Citation:
C. E. R. Alves, E. N. Cáceres, S. W. Song, "A BSP/CGM Algorithm for the All-Substrings Longest Common Subsequence Problem," ipdps, pp.57a, International Parallel and Distributed Processing Symposium (IPDPS'03), 2003
Usage of this product signifies your acceptance of the Terms of Use.