scientific article; zbMATH DE number 4047072

From MaRDI portal
Publication:3783528





[For the entire collection see Zbl 0633.00025.] This paper surveys randomized parallel algorithms found in the literature for various problems in computer science. In particular we will demonstrate the power of randomization as a tool for parallelizing sequential algorithms and introduce the reader to some of the techniques employed in designing randomized parallel algorithms. We consider representative problems from the following areas of computer science and describe how randomized parallel algorithms for these problems have been obtained: 1) routing and sorting, 2) processor load balancing, 3) algebra, and 4) graph theory. Finally we discuss methods of derandomizing randomized parallel algorithms.











This page was built for publication:

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