Experiments with parallel algorithms for combinatorial problems (Q1095034): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 02:10, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Experiments with parallel algorithms for combinatorial problems |
scientific article |
Statements
Experiments with parallel algorithms for combinatorial problems (English)
0 references
1988
0 references
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).
0 references
parallel computation
0 references
computational results
0 references
knapsack
0 references
shortest paths
0 references
branch and bound
0 references
divide and conquer
0 references