Generating combinations in parallel

DOI10.1007/BF01939357MaRDI QIDQ1082084zbMATH OpenFDO

Authors Becky Chan, Selim G. Akl

Publication date 1986

Published in BIT (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01939357

zbMATH Keywords

adaptive algorithmcost-optimal algorithmparallel algorithm

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

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.

Recommendations

• A parallel algorithm for generating combinations
• Parallel generation of permutations and combinations
• An optimal parallel algorithm for generating combinations
• New methods for the generation of permutations, combinations, and other combinatorial objects in parallel
• scientific article; zbMATH DE number 176751
• Spectral Analysis of an Oscillating Thermoviscoelastic Plate in a Transverse Magnetic Field
• On random and adaptive parallel generation of combinatorial objects
• scientific article; zbMATH DE number 3843149
• scientific article; zbMATH DE number 4131653
• scientific article; zbMATH DE number 4195879

Cites work

• Loopless Algorithms for Generating Permutations, Combinations, and Other Combinatorial Configurations
• Parallel Generation of Permutations

Cited in

(15)

• Parallel generation of permutations and combinations
• A simple systolic algorithm for generating combinations in lexicographic order
• A parallel algorithm for the generation of a permutation and applications
• A parallel algorithm for generating combinations
• A systolic generation of combinations
• New methods for the generation of permutations, combinations, and other combinatorial objects in parallel
• Listing combinatorial objects in parallel
• A Parallel Algorithm for Cost-Optimal Generation of Permutations ofrout ofnItems
• On random and adaptive parallel generation of combinatorial objects
• scientific article; zbMATH DE number 205341 (Why is no real title available?)
• A NEW METHOD FOR GENERATING INTEGER COMPOSITIONS IN PARALLEL
• A note on combination generators
• An optimal parallel algorithm for generating combinations
• Generating subsets on a systolic array
• An optimal algorithm for generating equivalence relations on a linear array of processors

This page was built for publication: Generating combinations in parallel

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1082084)