Parallel computing in combinatorial optimization |
| |
Authors: | G A P Kindervater J K Lenstra |
| |
Institution: | (1) Erasmus University, P.O. Box 1738, 3000 DR Rotterdam;(2) Centre for Mathematics and Computer Science, P.O. Box 4079, Amsterdam |
| |
Abstract: | This is a review of the literature on parallel computers and algorithms that is relevant for combinatorial optimization. We start by describing theoretical as well as realistic machine models for parallel computations. Next, we deal with the complexity theory for parallel computations and illustrate the resulting concepts by presenting a number of polylog parallel algorithms andP-completeness results. Finally, we discuss the use of parallelism in enumerative methods. |
| |
Keywords: | 90C27 68Q15 68Q25 68Rxx |
本文献已被 SpringerLink 等数据库收录! |
|