On Synchronous Parallel Computations with Independent Probabilistic Choice

DOI10.1137/0213004MaRDI QIDQ3347295zbMATH OpenOpenAlexFDO

Authors J. Reif

Publication date 1984

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0213004

zbMATH Keywords

parallel RAMparallel speedupperfect matchingprobabilistic algorithmsprobabilistic choiceprobabilistic computationprobabilistic RAMrandomized algorithmsynchronous parallel machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Algorithms in computer science (68W99)

Recommendations

• Parallelism in random access machines
• Probabilistic Parallel Algorithms for Sorting and Selection
• scientific article; zbMATH DE number 4047091
• Publication:4203821
• A fast and simple randomized parallel algorithm for the maximal independent set problem

Cited in

(13)

• Depth-first search is inherently sequential
• The probabilistic method yields deterministic parallel algorithms
• Simulating probabilistic by deterministic algebraic computation trees
• P-RAM vs. RP-RAM
• Randomized Gandy-Păun-Rozenberg machines
• scientific article; zbMATH DE number 4201596 (Why is no real title available?)
• scientific article; zbMATH DE number 3936481 (Why is no real title available?)
• Parallel computation for well-endowed rings and space-bounded probabilistic machines
• scientific article; zbMATH DE number 4057020 (Why is no real title available?)
• scientific article; zbMATH DE number 4062587 (Why is no real title available?)
• scientific article; zbMATH DE number 1262835 (Why is no real title available?)
• SEARCHING ALGORITHMS IMPLEMENTED ON PROBABILISTIC SYSTOLIC ARRAYS
• Optimal parallel algorithms on planar graphs

This page was built for publication: On Synchronous Parallel Computations with Independent Probabilistic Choice

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