An introduction to parallelism in combinatorial optimization
G.A.P. Kindervater, Jan Karel Lenstra · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 1985
This is a tutorial introduction to the literature on parallel computers and algorithms that is relevant for combinatorial optimization.We briefly discuss theoretical as well as realistic machine models and the complexity theory for parallel computations.Some examples of polylog parallel algorithms and log space completeness results for .<1'are given, and the use of parallelism in enumerative methods is reviewed.