MPI-INF/SWS Research Reports 1991-2021

1. Author,Editor - 3. with BibTeX cite keys


On a compaction theorem of ragde

Hagerup, Torben

November 1991, 6 pages.

Status: available - back from printing

Ragde demonstrated that in constant time a PRAM with $n$ processors can move at most $k$ items, stored in distinct cells of an array of size $n$, to distinct cells in an array of size at most $k^4$. We show that the exponent of 4 in the preceding sentence can be replaced by any constant greater than~2.

  • 91-121.pdf91-121.pdf
  • Attachement: 91-121.pdf (10473 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Hagerup, Torben},
  TITLE = {On a compaction theorem of ragde},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-91-121},
  MONTH = {November},
  YEAR = {1991},
  ISSN = {0946-011X},