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


Lower bounds for merging on the hypercube

Rüb, Christine

MPI-I-93-148. October 1993, 10 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
We show non-trivial lower bounds for several prefix problems in the
CRCW PRAM model. Our main result is an $\Omega(\alpha(n))$ lower bound
for the chaining problem, matching the previously known upper bound.
We give a reduction to show that the same lower bound applies to a
parenthesis matching problem, again matching the previously known
upper bound. We also give reductions to show that similar lower
bounds hold for the prefix maxima and the range maxima problems.
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-93-148.pdfMPI-I-93-148.pdf9040 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:
Hide details for BibTeXBibTeX
  AUTHOR = {R{\"u}b, Christine},
  TITLE = {Lower bounds for merging on the hypercube},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-93-148},
  MONTH = {October},
  YEAR = {1993},
  ISSN = {0946-011X},