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

Mannila, Heikki; Ukkonen, Esko

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