An introduction to parallelism in combinatorial optimization

AbstractThis 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 P are given, and the use of parallelism in enumerative methods is reviewed