Fast sequential and parallel algorithms for finding extremal sets

Hong Shen, D. J. Evans

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)

Abstract

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 & 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 O (log N) time algorithm using O (min {kN/log N, k2/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 1& contains multisets, and show that in this case the problem can be solved in O (min {N2/m2, k2mn/Iog 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.

Original languageEnglish
Pages (from-to)195-211
Number of pages17
JournalInternational Journal of Computer Mathematics
Volume61
Issue number3-4
DOIs
Publication statusPublished - 1996
Externally publishedYes

Keywords

  • Algorithms
  • Extremal set
  • Partial order
  • Set inclusion
  • Word-to-bit mapping

Fingerprint

Dive into the research topics of 'Fast sequential and parallel algorithms for finding extremal sets'. Together they form a unique fingerprint.

Cite this