×

Getting back to the past in the union-find problem. (English) Zbl 0644.68059

STACS 88, Theoretical aspects of computer science, Proc. 5th Annu. Symp., Bordeaux/France 1988, Lect. Notes Comput. Sci. 294, 8-17 (1988).
[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.

MSC:

68Q25 Analysis of algorithms and problem complexity
68R99 Discrete mathematics in relation to computer science
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Citations:

Zbl 0635.00015