Apostol Natsev, Alexander Haubold, et al.
MMSP 2007
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.
Apostol Natsev, Alexander Haubold, et al.
MMSP 2007
Yigal Hoffner, Simon Field, et al.
EDOC 2004
Ohad Shamir, Sivan Sabato, et al.
Theoretical Computer Science
Thomas R. Puzak, A. Hartstein, et al.
CF 2007