Experiments with parallel algorithms for combinatorial problems
In the last decade many models for parallel computation have been proposed and many parallel algorithms have been developed. However, few of these models have been realized and most of these algorithms are supposed to run on idealized, unrealistic parallel machines. The parallel machines constructed so far all use a simple model of parallel computation. Therefore, not every existing parallel machine is equally well suited for each type of algorithm. The adaptation of a certain algorithm to a specific parallel architecture may severely increase the complexity of the algorithm or severely obscure its essence. Little is known about the performance of some standard combinatorial algorithms on existing parallel machines. In this paper we present computational results concerning the solution of knapsack, shortest paths and change-making problems by branch and bound, dynamic programming, and divide and conquer algorithms on the ICL-DAP (an SIMD computer), the Manchester dataflow machine and the CDC-CYBER-205 (a pipeline computer).
- A note on two problems in connexion with graphs
- A Theorem on Boolean Matrices
- scientific article; zbMATH DE number 3126094 (Why is no real title available?)
- scientific article; zbMATH DE number 4027472 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- An extension of labeling techniques for finding shortest path trees
- Performance evaluation of vector implementations of combinatorial algorithms
- A parallel branch and bound algorithm for the quadratic assignment problem
- Branch-and-bound and parallel computation: A historical note
- Parallel processing for difficult combinatorial optimization problems
- Experiments with parallel branch-and-bound algorithms for the set covering problem
- Efficient massively parallel implementation of some combinatorial algorithms
- Conflicting criteria, cooperating processors - some experiments on implementing a multicriteria decision support method on a parallel computer
- Solving knapsack problems on GPU
- scientific article; zbMATH DE number 1262835 (Why is no real title available?)
- From the theory to the tools: parallel dynamic programming
This page was built for publication: Experiments with parallel algorithms for combinatorial problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1095034)
