MORE EFFICIENT PARALLEL TOTALLY MONOTONE MATRIX SEARCHING

We give a parallel algorithm for computing all row minima in a totally monotone n x n matrix which is simpler and more work efficient than p revious polylog-time algorithms. It runs in O(lg n lg lg n) time doing O(n root lg n) work on a CRCW PRAM, in O(lg n(lg lg n)(2)) time doing O(n root lg n) work on a CREW PRAM, and in O(lg n root lg n lg lg n) time doing O(n root lg n lg lg n) work on an EREW PRAM. Since finding the row minima of a totally monotone matrix has been shown to be funda mental in the efficient solution of a host of geometric and combinator ial problems, our algorithm leads directly to improved parallel soluti ons of many algorithms in terms of their work efficiency. (C) 1997 Aca demic Press.