## The set union problem with backtracking.(English)Zbl 0596.68039

Automata, languages and programming, Proc. 13th Int. Colloq., Rennes/France 1986, Lect. Notes Comput. Sci. 226, 236-243 (1986).
Summary: [For the entire collection see Zbl 0587.00019.]
The classical set union problem is to manipulate a partition of $$U=\{1,2,...,n\}$$ under the operations find an 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.

### MSC:

 68Q25 Analysis of algorithms and problem complexity 05A17 Combinatorial aspects of partitions of integers

deunion

Zbl 0587.00019