Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

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.pdfMPI-I-95-1-006.pdfMPI-I-95-1-006.dvi.gz20 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
Hide details for BibTeXBibTeX
@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},
}