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
February 1995, 12 pages.
.
Status: available - back from printing
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}.
-
MPI-I-95-1-006.pdf
- Attachement: MPI-I-95-1-006.dvi.gz (20 KBytes); MPI-I-95-1-006.pdf (106 KBytes)
URL to this document: https://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},
}