Experiments with parallel algorithms for combinatorial problems
type: Item
instance of: scholarly article
title: Experiments with parallel algorithms for combinatorial problems
zbMATH Open document ID: 0631.90052
DOI: 10.1016/0377-2217(88)90255-X
author: G. A. P. Kindervater
author: Harry W. J. M. Trienekens
published in: European Journal of Operational Research
publication date: 1988-01-01T00:00:00Z
review text: 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).
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 4027177
zbMATH Keywords: parallel computation
zbMATH Keywords: computational results
zbMATH Keywords: knapsack
zbMATH Keywords: shortest paths
zbMATH Keywords: branch and bound
zbMATH Keywords: divide and conquer
describes a project that uses: Algorithm 97
describes a project that uses: Sisal
MaRDI profile type: Publication
cites work: Q3241581
cites work: A note on two problems in connexion with graphs
cites work: Q4198056
cites work: Q3768905
cites work: A Theorem on Boolean Matrices
full work available at URL: 0377-2217(88)90255-x
OpenAlex ID: W2618995073
description: scientific article; zbMATH DE number 4027177