We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
TIme Optimal n-Size Matching Parentheses and Binary Tree Decoding Algorithms on a p-Processor BSR.
- Authors
Xiang, Limin; Ushijima, Kazuo; Zhao, Jianjun; Akl, S.
- Abstract
Time optimal algorithms on an n-processor BSR PRAM for many n-size problems can be found in the literature. They outpace those on EREW, CREW or CRCW PRAM for the same problems. When only p (1 < p < n) processors are available, efficient algorithms on a p-processor BSR for some n-size problems can not be obtained from those on an n-processor BSR, and they have to be reconsidered. In this paper, we discuss and give two algorithms on a p-processor BSR for the two n-size problems of matching parentheses and decoding a binary tree from its bit-string, respectively, and show that they are time optimal.
- Subjects
PARALLEL algorithms; PARALLEL processing
- Publication
Parallel Processing Letters, 2002, Vol 12, Issue 3/4, p365
- ISSN
0129-6264
- Publication type
Article
- DOI
10.1142/S0129626402001051