A simple randomized parallel algorithm for list-ranking

DOI10.1016/0020-0190(90)90196-5MaRDI QIDQ911268zbMATH OpenOpenAlexWikidataFDO

Authors Richard J. Anderson, Gary L. Miller

Publication date 1990

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(90)90196-5

zbMATH Keywords

analysis of algorithmsparallel processingEREW PRAM

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Theory of operating systems (68N25)

Recommendations

• Practical parallel list ranking
• Deterministic parallel list ranking
• scientific article; zbMATH DE number 4064468
• scientific article; zbMATH DE number 1444289
• Efficient ranking and selection in parallel computing environments
• On the complexity of list ranking in the parallel external memory model
• Faster optimal parallel prefix sums and list ranking

Cites work

• An Efficient Parallel Biconnectivity Algorithm
• The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time

Cited in

(12)

• Deterministic coin tossing with applications to optimal parallel list ranking
• A new family of randomized algorithms for list accessing
• Randomized parallel list ranking for distributed memory multiprocesors
• Adapting parallel algorithms to the W-stream model, with applications to graph problems
• scientific article; zbMATH DE number 4064468 (Why is no real title available?)
• List-ranking on interconnection networks.
• Efficient massively parallel implementation of some combinatorial algorithms
• scientific article; zbMATH DE number 1444289 (Why is no real title available?)
• One-by-one cleaning for practical parallel list ranking
• Faster optimal parallel prefix sums and list ranking
• Efficient list ranking on the reconfigurable mesh, with applications
• Randomized parallel list ranking for distributed memory multiprocessors.

This page was built for publication: A simple randomized parallel algorithm for list-ranking

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