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.
Recommendations
Cited in
(6)- Worst-case analysis of the set-union problem with extended backtracking
- A partially persistent data structure for the set-union problem
- scientific article; zbMATH DE number 3960991 (Why is no real title available?)
- Fully persistent data structures for disjoint set union problems
- The Set Union Problem with Unlimited Backtracking
- The set union problem with dynamic weighted backtracking
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)