On a compaction theorem of ragde

Hagerup, Torben

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Report

On a compaction theorem of ragde

MPS-Authors

/persons/resource/persons44564

Hagerup, Torben
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

91-121.pdf
(Any fulltext), 11MB

Supplementary Material (public)

There is no public supplementary material available

Citation

Hagerup, T.(1991). On a compaction theorem of ragde (MPI-I-91-121). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-B053-E

Abstract

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.