Westbrook, Jeffery; Tarjan, Robert E. Amortized analysis of algorithms for set union with backtracking. (English) Zbl 0679.68039 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č Cited in 1 ReviewCited in 4 Documents 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 Citations:Zbl 0614.68064 PDF BibTeX XML Cite \textit{J. Westbrook} and \textit{R. E. Tarjan}, SIAM J. Comput. 18, No. 1, 1--11 (1989; Zbl 0679.68039) Full Text: DOI OpenURL