No label defined (Q3787478)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4050989
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4050989 |
Statements
1988
0 references
union-find problem
0 references
set union problem
0 references
backtracking
0 references
data structure
0 references
space \(\times \,time\) complexity
0 references
0.9396178126335144
0 references
0.9290297031402588
0 references
0.9215092658996582
0 references
0.8568252325057983
0 references
[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.
0 references