Finding the maximum subsequence sum on interconnection networks
Title:
Finding the maximum subsequence sum on interconnection networks
Author:
Qiu, K. Akl, S. G.
Appeared in:
International journal of parallel, emergent and distributed systems
Paging:
Volume 22 (2007) nr. 5 pages 371-385
Year:
2007-01
Contents:
We develop parallel algorithms for the maximum subsequence sum (or maximum sum for short) problem on several interconnection networks. For the 1-D version of the problem, we find an algorithm that computes the maximum sum of N elements on these networks of size p, where p ≤ N, with a running time of [image omitted] , which is optimal in view of the [image omitted] lower bound. When [image omitted] , our algorithm computes the maximum sum in O(log N) time, resulting in an optimal cost of O(N). This result also matches the performance of two previous algorithms that are designed to run on the more powerful PRAM model. Our 1-D maximum sum algorithm can be used to solve the problem of maximum subarray, the 2-D version of the problem. In particular, for the same interconnection networks studied here, our parallel algorithm finds the maximum subarray of an N × N array in time O(log N) with [image omitted] processors, once again, matching the performance of a previous PRAM algorithm.
Journal description