TY - JOUR

T1 - Fully dynamic algorithms for maintaining extremal sets in a family of sets

AU - Shen, Hong

N1 - Funding Information:
*This work was partially supported by Australia Research Council under its Small Grants Scheme.

PY - 1998

Y1 - 1998

N2 - 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 setcontents 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 F, we present a set of algorithms that, requiring a space of O(N + kn/log N + k2) words, process in O(l) 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 O(kn/log N) extra words in space within the same bound O(N2), improve the time complexity of the existing result [9] by a factor of O(N).

AB - 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 setcontents 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 F, we present a set of algorithms that, requiring a space of O(N + kn/log N + k2) words, process in O(l) 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 O(kn/log N) extra words in space within the same bound O(N2), improve the time complexity of the existing result [9] by a factor of O(N).

KW - Dynamic algorithm

KW - Extremal set query

KW - Partial order

KW - Set deletion

KW - Set insertion

UR - http://www.scopus.com/inward/record.url?scp=11744379137&partnerID=8YFLogxK

U2 - 10.1080/00207169808804719

DO - 10.1080/00207169808804719

M3 - Article

AN - SCOPUS:11744379137

SN - 0020-7160

VL - 69

SP - 203

EP - 215

JO - International Journal of Computer Mathematics

JF - International Journal of Computer Mathematics

IS - 3-4

ER -