No label defined (Q4247467)

The aim of the paper is to survey basic parallel randomized algorithms for some discrete problems. In particular, the author presents algorithms used for sorting, packet routing, shortest paths problems, matching problems, depth first search, minimum cost spanning trees, maximal independent set problems and network flow problems. The paper begins with a preliminary section which provides the basic notations and definitions adopted in the rest of the paper (parallel models of computing, randomized algorithms, Chernoff bounds, complexity classes NC, RNC). The algorithms for sorting on PRAM, Mesh and Hypercube are described in brief and their properties -- run time complexity and the number of processors -- are presented in the tables. Section ``Packet Routing'' and all following sections are already written in the usual mathematical style. A routing algorithm on \(n\times n\) Mesh with \((2+\varepsilon)n\) runtime for any fixed \(\varepsilon\geq 1/\log n\) is described. For routing on undirected graphs with \(n\) vertices and \(m\) edges an algorithm is presented with \(O(\sqrt n)\) run time and \(m\log n\) processors. The section devoted to matching problems recalls namely important Tutte's result found in the 1947. A randomized algorithm using Tutte matrix for perfect matching in a graph is presented. This section also contains several useful lemmas concerning computation complexity and equivalence between some routing problems and perfect matching in a graph. The section ``Luby's Method'' is devoted to an important randomized technique for optimization problems. This method is presented by describing an efficient algorithm for Maximal Independent Set problem. In the section ``Randomization and approximation'' the authors focus on the MAX FLOW problem for networks. They prove several lemmas and a theorem which states the MAX FLOW problem belong to the complexity class RNC (polylogarithmic run time, polynomial number of processors and randomized algorithms). This well-written paper is a valuable survey of some basic randomization techniques for efficient parallel algorithms and may be highly recommended. For the entire collection see [Zbl 0914.90002].