Finding least-weight subsequences with fewer processors

Abstract

By restricting weight functions to satisfy the quadrangle inequality or the inverse quadrangle inequality, significant progress has been made in developing efficient sequential algorithms for the least-weight subsequence problem [10], [9], [12], [16]. However, not much is known on the improvement of the naive parallel algorithm for the problem, which is fast but demands too many processors (i.e., it takes O(log 2n) time on a CREW PRAM with n 3/log n processors). In this paper we show that if the weight function satisfies the inverse quadrangle inequality, the problem can be solved on a CREW PRAM in O(log 2n log log n) time with n/log log n processors, or in O(log 2n) time with n log n processors. Notice that the processor-time complexity of our algorithm is much closer to the almost linear-time complexity of the best-known sequential algorithm [12]. © 1993 Springer-Verlag New York Inc.