scientific article; zbMATH DE number 4047072
Research exposition (monographs, survey articles) pertaining to computer science (68-02) Theory of operating systems (68N25) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Symbolic computation and algebraic computation (68W30) Algorithms in computer science (68W99)
[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.
- An efficient parallel algorithm for random sampling
- A randomized parallel branch-and-bound algorithm
- From randomizing polynomials to parallel algorithms
- scientific article; zbMATH DE number 3978375 (Why is no real title available?)
- A randomized parallel backtracking algorithm
- scientific article; zbMATH DE number 176073 (Why is no real title available?)
- scientific article; zbMATH DE number 1302200 (Why is no real title available?)
- Randomized parallel algorithms
- scientific article; zbMATH DE number 1857643 (Why is no real title available?)
- scientific article; zbMATH DE number 1857646 (Why is no real title available?)
- Time-Randomness Trade-offs in Parallel Computation
- scientific article; zbMATH DE number 1419211 (Why is no real title available?)
- scientific article; zbMATH DE number 1419212 (Why is no real title available?)
- scientific article; zbMATH DE number 1419213 (Why is no real title available?)
- scientific article; zbMATH DE number 1419214 (Why is no real title available?)
- Random seeking: a general, efficient, and informed randomized scheme for dynamic load balancing
- Parallelism in random access machines
- 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)