×

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.

MSC:
68Q25 Analysis of algorithms and problem complexity
05A17 Combinatorial aspects of partitions of integers
Keywords:
deunion