Generating combinations in parallel
type: Item
instance of: scholarly article
title: Generating combinations in parallel
zbMATH Open document ID: 0602.68057
DOI: 10.1007/BF01939357
author: Becky Chan
author: Selim G. Akl
published in: BIT
publication date: 1986-01-01T00:00:00Z
review text: A parallel algorithm for generating all combinations of m out of n items in lexicographic order is presented. The algorithm uses m processors and runs in O(nCm) time. The cost of the algorithm, which is the parallel running time multiplied by the number of processors used, is optimal to within a constant multiplicative factor in view of the \(\Omega\) (nCm*m) lower bound on the number of operations required to solve this problem using a sequential computer.
Mathematics Subject Classification ID: 68R99
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05A05
zbMATH DE Number: 3972208
zbMATH Keywords: adaptive algorithm
zbMATH Keywords: cost-optimal algorithm
zbMATH Keywords: parallel algorithm
MaRDI profile type: Publication
cites work: Loopless Algorithms for Generating Permutations, Combinations, and Other Combinatorial Configurations
cites work: Parallel Generation of Permutations
Recommended article: A parallel algorithm for generating combinations
Recommended article: Parallel generation of permutations and combinations
Recommended article: An optimal parallel algorithm for generating combinations
Recommended article: New methods for the generation of permutations, combinations, and other combinatorial objects in parallel
Recommended article: Q4036581
Recommended article: Spectral Analysis of an Oscillating Thermoviscoelastic Plate in a Transverse Magnetic Field
Recommended article: On random and adaptive parallel generation of combinatorial objects
Recommended article: Q3313272
Recommended article: Q3033316
Recommended article: Q5202618
description: scientific article; zbMATH DE number 3972208