More Efficient Parallel Totally Monotone Matrix Searching
✍ Scribed by Phillip G Bradford; Rudolf Fleischer; Michiel Smid
- Publisher
- Elsevier Science
- Year
- 1997
- Tongue
- English
- Weight
- 207 KB
- Volume
- 23
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
We give a parallel algorithm for computing all row minima in a totally monotone n = n matrix which is simpler and more work efficient than previous polylog-time Ž . Ž . algorithms. It runs in O lg n lg lg n time doing O n lg n work on a CRCW ' 2 Ž Ž . . Ž . PRAM, in O lg n lg lg n time doing O n lg n work on a CREW PRAM, and in ' Ž . Ž . O lg n lg n lg lg n time doing O n 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 fundamental in the efficient solution of a host of geometric and combinatorial problems, our algorithm leads directly to improved parallel solutions of many algorithms in terms of their work efficiency.