MPI-INF/SWS Research Reports 1991-2021
2. Number - only D1
MPI-I-91-121
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.pdf
- Attachement: 91-121.pdf (10473 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1991-121
BibTeX@TECHREPORT{Hagerup91b,
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},
}