scientific article; zbMATH DE number 4050989

From MaRDI portal
Publication:3787478





[For the entire collection see Zbl 0635.00015.] We consider an extension of the well known set union problem, where backtracking over the union operations is possible. A data structure is presented which maintains a partition of an n-item set and performs each union in O(log log n) time, each find in O(log n) time and allows backtracking over the unions in O(1) time. The space complexity is O(n). The data structure favorably compares with other data structures proposed in the literature for such a problem also from the space \(\times time\) complexity point of view.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3787478)