Ziyang Liu, Sivaramakrishnan Natarajan, et al.
VLDB
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.
Ziyang Liu, Sivaramakrishnan Natarajan, et al.
VLDB
Yao Qi, Raja Das, et al.
ISSTA 2009
Corneliu Constantinescu
SPIE Optical Engineering + Applications 2009
Rajiv Ramaswami, Kumar N. Sivarajan
IEEE/ACM Transactions on Networking