AN OPTIMAL ALGORITHM FOR GENERATING EQUIVALENCE-RELATIONS ON A LINEAR-ARRAY OF PROCESSORS

作     者：STOJMENOVIC, I 

作者机构：UNIV OTTAWA DEPT COMP SCI OTTAWA K1N 9B4 ONTARIO CANADA UNIV NOVI SAD INST MATH YU-21000 NOVI SAD YUGOSLAVIA 

出 版 物：《BIT NUMERICAL MATHEMATICS》 (BIT数值数学)

年 卷 期：1990年第30卷第3期

页      面：424-436页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0835[工学-软件工程] 0701[理学-数学] 

主　　题：C.1 F.2 parallel algorithm linear array subsets equivalence relations 

摘      要：We describe a cost-optimal parallel algorithm for enumerating all partitions (equivalence relations) of the set {1, ...,n}, in lexicographic order. The algorithm is designed to be executed on a linear array of processors. It usesn processors, each having constant size memory and each being responsible for producing one element of a given set partition. Set partitions are generated with constant delay leading to anO(B n) time solution, whereB n is the total number of set partitions. The same method can be generalized to enumerate some other combinatorial objects such as variations. The algorithm can be made adaptive, i.e. to run on any prespecified number of processors. To illustrate the model of parallel computation, a simple case of enumerating subsets of the set {1, ...,n}, having at mostm (≤n) elements is also described.