We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Parallel Range Minima on Coarse Grained Multicomputers.
- Authors
Mongelli, H.; Song, S. W.; Olariu, S.
- Abstract
Given an array of n real numbers A = (a[SUBo],a[SUBl],...,a[SUBn-1]), define MIN(i,j) = min{a[SUBi],...,a[SUBj]}. The range minima problem consists of preprocessing array A such that queries MIN(i,j), for any 0 ≤ i ≤ j ≤ n - i can be answered in constant time. Range minima is a basic problem that appears in many other important graph problems such as lowest common ancestor, Euler tour, etc. In this work we present a parallel algorithm under the CGM model (coarse grained multicomputer), that solves the range minima problem in O(n/p) time and constant number of communication rounds. The communication overhead involves the transmission of p numbers (independent of n). We show promising experimental results with speedup curves approximating the optimal for large n.
- Subjects
MAXIMA &; minima; ARRAY processors; COMPUTER systems; PARALLEL algorithms
- Publication
International Journal of Foundations of Computer Science, 1999, Vol 10, Issue 4, p375
- ISSN
0129-0541
- Publication type
Article
- DOI
10.1142/S0129054199000277