Parallel algorithmic techniques for combinatorial computation. (English) Zbl 0691.68037

Eppstein, David; Galil, Zvi

Automata, languages and programming, Proc. 16th Int. Colloq., Stresa/Italy 1989, Lect. Notes Comput. Sci. 372, 303-318 (1989).

[For the entire collection see Zbl 0681.00016.]
The paper briefly describes a number of basic techniques for designing parallel algorithms for solving combinatorial problems on graphs for a shared memory model of parallel computation. Types of concurrent memory access used and their mutual simulation are briefly discussed.
The techniques discussed deal with prefix computation and ranking, graph (in particular, tree) traversals and decompositions, matrix calculations. The model of parallelism adopted allows also randomization of algorithms for some problems.
A number of applications of these algorithmic tools are described or listed.

Reviewer: N.Korneenko

MSC:

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

Keywords:

parallel prefix; parallel algorithms; randomization

Citations:

Zbl 0681.00016