Amortized analysis of algorithms for set union with backtracking. (English) Zbl 0679.68039

The problem called set union with backtracking introduced by H. Mannila and E. Ukkonen [Lect. Notes Comput. Sci. 225, 122-133 (1986; Zbl 0614.68064)] as a generalization of the classical disjoint set union problem is considered, and the amortized time of this problem (the time of an operation averaged over a worst-case sequence of operations) is analyzed. The only difference between the classical problem and the new one is that the set union with backtracking has one new, additional operation:
de-union: Undo the most recently performed union operation that has not yet been undone. The reason to add this new operation arises in Prolog interpreter memory management.
Several algorithms for this problem are analyzed. The best algorithms runs in amortized time 0(log n/log log n), where n is the total number of elements in the sets. For the class of separable pointer-based algorithms also a tight lower bound is achieved.
Reviewer: J.Hromkovič


68P05 Data structures
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science


Zbl 0614.68064
Full Text: DOI