The set union problem with backtracking

This work studies a variant of the classical set union problem, where backtracking over the union operations is possible with the deunion operation, and develops an implementation to on-line perform an intermixed sequence of m finds, k unions and at most k deunions in O((m+k) log log n) steps.

Abstract

The classical set union problem is to manipulate a partition of U = {1,2,...,n} under the operations find and union. We study a variant of this problem, where backtracking over the union operations is possible with the deunion operation. An implementation is developed to on-line perform an intermixed sequence of m finds, k unions and at most k deunions in O((m+k) log log n) steps. An O(k + m log n) method is also given. The problem considered is motivated by questions arising in the implementation of the programming language Prolog.