Finding extremal sets in less than quadratic time

Abstract

We consider the problem of finding the minimal and maximal sets in a family F of sets, i.e. a collection of subsets of some domain. For a family of sets of size N we give an algorithm which finds these extremal sets in expected time O(N2/log N), and worst case time O(N2/√log N). All previous algorithms had worst case complexity of ω(N2). We also present a simple algorithm for dynamically recomputing the minimal and maximal sets as elements are inserted to and deleted from the subsets. This algorithm has a worst case bound of O(N) per update, and this bound is tight. © 1993.