Fully Dynamic Algorithms for Maintaining Extremal Sets in A Family of Sets

The extremal sets of a family F of sets consist of all minimal and maximal sets of F that have no subset and superset in F respectively. We consider the problem of efficiently maintaining all extremal sets in F when it undergoes dynamic updates including set insertion, deletion and set-contents update (insertion, deletion and value update of elements). Given F containing k sets with N elements and domain (the union of these sets) size n, where clearly k; n N for any F , we present a set of algorithms that, requiring a space of O(N + kn log N + k 2 ) words, process in O(1) time a query on whether a set of F is minimal and/or maximal, and maintain all extremal sets of F in O(N ) time per set insertion in the worst case, deletion and set-contents update. Both time bounds are tight. Our algorithms are the first known fully dynamic algorithms that answer an extremal set query in constant time and maintain extremal sets in linear time for any set insertion and deletion. Keywords: Dy..