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

Westbrook, Jeffery; Tarjan, Robert E.

SIAM J. Comput. 18, No. 1, 1-11 (1989).

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č

MSC:

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

Keywords:

data structures; logic programming; set union problem; backtracking