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

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


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


Zbl 0681.00016