zbMATH — the first resource for mathematics

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.

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