Fully dynamic algorithms for maintaining extremal sets in a family of sets^∗

^∗This work was partially supported by Australia Research Council under its Small Grants Scheme.

Abstract

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 in total and domain (the union of these sets) size n, where clearly k n ≤ N for any ℱ, we present a set of algorithms that, requiring a space of 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, deletion and set-contents update in the worst case. Our algorithms are the first linear-time fully dynamic algorithms for maintaining extremal sets, which, requiring extra words in space within the same bound O(N ²), improve the time complexity of the existing result [9] by a factor of O(N).

Keywords:

• Dynamic algorithm
• extremal set query
• partial order
• set deletion
• set insertion

C.R. Categories:

• F.4.3
• F.2.2

^∗This work was partially supported by Australia Research Council under its Small Grants Scheme.

^∗This work was partially supported by Australia Research Council under its Small Grants Scheme.

Notes

^∗This work was partially supported by Australia Research Council under its Small Grants Scheme.