max planck institut
informatik

# MPI-I-95-1-006

## A polylog-time and $O(n\sqrt\lg n)$-work parallel algorithm for finding the row minima in totally monotone matrices

### Bradford, Phillip G. and Fleischer, Rudolf and Smid, Michiel

MPI-I-95-1-006. February 1995, 12 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
We give a parallel algorithm for computing all row minima
in a totally monotone $n\times 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\sqrt{\lg n})$ work on a {\sf CRCW}, in
$O(\lg n (\lg\lg n)^2)$ time doing $O(n\sqrt{\lg n})$ work on a {\sf CREW},
and in $O(\lg n\sqrt{\lg n \lg\lg n})$ time
doing $O(n\sqrt{\lg n\lg\lg n})$ work on an {\sf EREW}.
Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-95-1-006.pdf20 KBytes; 106 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1995-1-006
BibTeX
TITLE = {A polylog-time and $O(n\sqrt{\lg n})$-work parallel algorithm for finding the row minima in totally monotone matrices},