Donald Samuels, Ian Stobert
SPIE Photomask Technology + EUV Lithography 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.
Donald Samuels, Ian Stobert
SPIE Photomask Technology + EUV Lithography 2007
Alessandro Morari, Roberto Gioiosa, et al.
IPDPS 2011
Leo Liberti, James Ostrowski
Journal of Global Optimization
Frank R. Libsch, S.C. Lien
IBM J. Res. Dev