More Efficient Parallel Totally Monotone Matrix Searching |
| |
Authors: | Phillip G Bradford Rudolf Fleischer Michiel Smid |
| |
Institution: | aMax-Planck-Institut für Informatik, Im Stadtwald, D-666123, Saarbrücken, Germany;bFakultät für Informatik, Otto-von-Guericke-Universität Magdeburg, D-39106, Magdeburg, Germany |
| |
Abstract: | We give a parallel algorithm for computing all row minima in a totally monotonen × nmatrix which is simpler and more work efficient than previous polylog-time algorithms. It runs inO(lg n lg lg n) time doingwork on aCRCW PRAM, inO(lg n(lg lg n)2) time doingwork on aCREW PRAM, and intime doingwork on anEREW 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|