Worst-case analysis of the set-union problem with extended backtracking. (English) Zbl 0678.68035

Summary: An extension of the well known set union problem is considered, where backtracking over sequences of Union operations is allowed. A data structure is presented which maintains a partition of an n-item set making it possible to perform each Union in 0(lg lg n) time, each Find in 0(lg n) time and allows backtracking over the Unions in 0(1) time. Moreover, it is shown that the data structure can be slightly modified as to present an \(0(k+m lg n)\) time complexity on a sequence of k Unions and Backtracks and m Finds. The space complexity of both versions of such a data structure is 0(n).


68Q25 Analysis of algorithms and problem complexity
68Q60 Specification and verification (program logics, model checking, etc.)
05A17 Combinatorial aspects of partitions of integers
68R99 Discrete mathematics in relation to computer science
Full Text: DOI


[1] Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1972), Addison-Wesley New York · Zbl 0207.01701
[2] Adelson-Velskii, G.M.; Landis, Y.M., An algorithm for the organization of the information, Soviet math. dokl., 3, 1259-1262, (1962)
[3] Blum, N., On the single operation worst-case time complexity of the disjoint set union problem, SIAM J. comput., 15, 1021-1024, (1986) · Zbl 0619.68039
[4] Bollobas, B.; Simon, I., On the expected behaviour of disjoint set union problems, Proc. 17th ACM symp. on theory of computing, 224-231, (1985)
[5] Bayer, R.; McCreight, E., Organization and maintenance of large ordered indices, Acta inform., 1, 173-179, (1972) · Zbl 0226.68008
[6] Gaibisso, C.; Gambosi, G.; Talamo, M., A partially persistent data structure for the set-union problem, RAIRO—theoretical informatics and applications, (1989), to be published · Zbl 0701.68021
[7] Gambosi, G.; Italiano, G.F.; Talamo, M., Getting back to the past in the union-find problem, 5th symp. on theoretical aspects of computer science, 8-17, (1988) · Zbl 0644.68059
[8] G. Gambosi, G.F. Italiano and M. Talamo, The Union-Find problem with dynamic weighted backtracking, Algorithmica, submitted. · Zbl 0727.68040
[9] Gabow, H.N.; Tarjan, R.E., A linear time algorithm for a special case of disjoint set union, Proc. 15th ACM symp. on theory of computing, 246-251, (1983)
[10] Hogger, C.J., Introduction to logic programming, (1984), Academic Press New York · Zbl 0572.68009
[11] Hopcroft, J.E.; Ullman, J.D., Set merging algorithms, SIAM J. comput., 2, 294-303, (1973) · Zbl 0253.68003
[12] Loebl, M.; Nešetřil, J., Linearity and unprovability of set union problems, Proc. 20th ACM symp. on theory of computing, 360-366, (1988)
[13] Mannila, H.; Ukkonen, E., The set union problem with backtracking, Proc. 13th ICALP, 236-243, (1986)
[14] Mannila, H.; Ukkonen, E., On the complexity of unification sequences, Proc. 3rd conf. on logic programming, 122-133, (1986)
[15] Mehlhorn, K.; Naher, S.; Alt, H., A lower bound for the complexity of the union-split-find problem, Proc. 14th ICALP, 479-488, (1987) · Zbl 0635.68033
[16] Nievergelt, J.; Reingold, E.M., Binary search trees of bounded balance, SIAM J. comput., 2, 33-43, (1973) · Zbl 0262.68012
[17] Pearl, J., Heuristics, (1984), Addison-Wesley Reading, MA
[18] Tarjan, R.E., Efficiency of a good but not linear set union algorithms, J. ACM, 22, 215-225, (1975) · Zbl 0307.68029
[19] Tarjan, R.E., A class of algorithms which require nonlinear time to maintain disjoint sets, J. comput. sys. sci., 18, 110-127, (1979) · Zbl 0413.68039
[20] Tarjan, R.E., Amortized computational complexity, SIAM J. alg. discr. meth., 6, 306-318, (1985) · Zbl 0599.68046
[21] Tarjan, R.E.; van Leeuwen, J., Worst-case analysis of set union algorithms, J. ACM, 31, 245-281, (1984) · Zbl 0632.68043
[22] van Leeuwen, J.; van der Weide, T., Alternative path compression techniques, ()
[23] Warren, D.H.D.; Pereira, L.M., Prolog-the language and its implementation compared with LISP, ACM SIGPLAN notices, 12, 109-115, (1977)
[24] Westbrook, J.; Tarjan, R.E., Amortized analysis of algorithms for set union with backtracking, () · Zbl 0679.68039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.