A note on set union with arbitrary deunions
Zvi Galil, Giuseppe Francesco Italiano · Information Processing Letters · 1991
Abstract We consider a variant of the set union problem, called set union with arbitrary deunions, that consists of maintaining a collection of disjoint sets under three kinds of operations: union, find, and deunion(i). A deunion(i) undoes the ith union performed so far and not yet undone. Each operation can be supported in O(log n) time in the worst-case, where n is the total number of items in the collection of disjoint sets. Motivations for this problem arise in logic programming memory management.