O (^* n) algorithms on a Sum-CRCW PRAM

DOI10.1007/S00607-006-0214-YzbMATH Open1111.68145OpenAlexW2144841199MaRDI QIDQ873150FDOQ873150

Stanley C. Eisenstat

Publication date: 28 March 2007

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00607-006-0214-y

zbMATH Keywords

parallel random access machinelinear integer sortingparallel prefix sums

Mathematics Subject Classification ID

Searching and sorting (68P10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Parallel algorithms in computer science (68W10)

Cited In (5)

• \(O(\log \log n)\)-time integer geometry on the CRCW PRAM
• Computing OR on a randomized fixed adversary CRCW PRAM
• Time lower bounds do not exist for CRCW PRAMs
• Computing with Spikes: The Advantage of Fine-Grained Timing
• An Improved Parallel Prefix Sums Algorithm

Recommendations

• Title not available (Why is that?) 👍 👎
• Computing OR on a randomized fixed adversary CRCW PRAM 👍 👎
• Optimal bounds for decision problems on the CRCW PRAM 👍 👎
• Time lower bounds do not exist for CRCW PRAMs 👍 👎
• Lower bounds for randomized exclusive write PRAMs 👍 👎
• \(O(\log \log n)\)-time integer geometry on the CRCW PRAM 👍 👎
• Fast and optimal simulations between CRCW PRAMs 👍 👎
• Lower bounds for recognizing small cliques on CRCW PRAM's 👍 👎
• PRAM processor allocation: a hidden bottleneck in sublogarithmic algorithms 👍 👎

This page was built for publication: \(O (\log^* n)\) algorithms on a Sum-CRCW PRAM

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q873150)