Randomized parallel computation


Journal Article

© Springer-Verlag Berlin Heidelberg 1987. 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.

Full Text

Duke Authors

Cited Authors

  • Rajasekaran, S; Reif, JH

Published Date

  • January 1, 1987

Published In

Volume / Issue

  • 278 LNCS /

Start / End Page

  • 364 - 376

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

Digital Object Identifier (DOI)

  • 10.1007/3-540-18740-5_79

Citation Source

  • Scopus