caa a22 4500 465821227 CHVBK 20180323112136.0 cr unu---uuuuu 170327e19900901xx s 000 0 eng 10.1007/BF01931658 doi (NATIONALLICENCE)springer-10.1007/BF01931658 Stojmenović Ivan Computer Science Department, University of Ottawa, K1N 9B4, Ottawa, Ontario, Canada aut An optimal algorithm for generating equivalence relations on a linear array of processors [Elektronische Daten] [Ivan Stojmenović] 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. BIT Foundations, 1990 C.1 nationallicence F.2 nationallicence parallel algorithm nationallicence linear array nationallicence subsets nationallicence equivalence relations nationallicence BIT Numerical Mathematics Kluwer Academic Publishers 30/3(1990-09-01), 424-436 0006-3835 30:3<424 1990 30 10543 https://doi.org/10.1007/BF01931658 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF01931658 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Stojmenović Ivan Computer Science Department, University of Ottawa, K1N 9B4, Ottawa, Ontario, Canada aut NATIONALLICENCE 773 0- BIT Numerical Mathematics Kluwer Academic Publishers 30/3(1990-09-01), 424-436 0006-3835 30:3<424 1990 30 10543 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer