# 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.pdf | 20 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**
`@TECHREPORT{``BradfordFleischerSmid95``,`

` AUTHOR = {Bradford, Phillip G. and Fleischer, Rudolf and Smid, Michiel},`

` TITLE = {A polylog-time and $O(n\sqrt{\lg n})$-work parallel algorithm for finding the row minima in totally monotone matrices},`

` TYPE = {Research Report},`

` INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},`

` ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},`

` NUMBER = {MPI-I-95-1-006},`

` MONTH = {February},`

` YEAR = {1995},`

` ISSN = {0946-011X},`

`}`