Finding extremal sets on the GPU

• We present parallel algorithms designed under CUDA for finding the extremal sets of a family FF of sets.
• We solve either the maximal or the minimal sets problem.
• The complexity analysis of the presented algorithms is provided.
• Algorithms are experimentally tested and several results are provided.

The extremal sets of a family FF of sets consist of all sets of FF that are maximal or minimal with respect to the partial order induced by the subset relation in FF. In this paper we present efficient parallel GPU-based algorithms, designed under CUDA architecture, for finding the extremal sets of a family FF of sets. The complexity analysis of the presented algorithms together with experimental results showing the efficiency and scalability of the approach is provided.