Result: Fast sequential and parallel algorithms for finding extremal sets

We consider the problem of finding the minimal (maximal) sets of a family of sets that have no subset (superset) in the family. Given a family F of k sets with N elements and a domain of size n, first we show that using word-to-bit mapping, a technique of compressing words into bits and processing bits instead of words, we can obtain a simple algorithm that solves this problem in O (N log N + min {kN, k2n/log N}) time using O (N + (k2/log N)) space in the worst case. When kn=Θ(N) and n=Ω(log N), our algorithm runs in O(N2/log2N) time and O(N2/log3N) space, thus improving known results. We then present two fast parallel algorithms for solving this problem - an 0 (log N) time algorithm using O(min{kN/log N, k2n/log2N}) processors on a CREW PRAM and a constant-time algorithm using O(nN + min {kN, k2n/log N}) processors on a combining CRCW PRAM in which concurrent writing is resolved by writing the sum of the individual values to be written. These are respectively the first NC algorithm on the CREW and constant-time algorithm on the CRCW for the extremal set problem. Finally we extend the extremal set problem to the case when F contains multisets, and show that in this case the problem can be solved in O(min {N2/m2,k2mn/log N}) time and O(N + (k2/log N)) space when the maximal number of duplicates of any element within a multiset is m and all duplicates are uniformly distributed.