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

DOI10.1007/S00607-006-0214-YMaRDI QIDQ873150zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 1308942
• Time lower bounds do not exist for CRCW PRAMs
• Computing OR on a randomized fixed adversary CRCW PRAM
• \(O(\log \log n)\)-time integer geometry on the CRCW PRAM
• Optimal bounds for decision problems on the CRCW PRAM
• Lower bounds for recognizing small cliques on CRCW PRAM's
• PRAM processor allocation: a hidden bottleneck in sublogarithmic algorithms
• Fast and optimal simulations between CRCW PRAMs
• Lower bounds for randomized exclusive write PRAMs

Cited in

(5)

• An Improved Parallel Prefix Sums Algorithm
• Computing OR on a randomized fixed adversary CRCW PRAM
• \(O(\log \log n)\)-time integer geometry on the CRCW PRAM
• Computing with spikes: the advantage of fine-grained timing
• Time lower bounds do not exist for CRCW PRAMs

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)