A partially persistent data structure for the set-union problem
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 24 (1990) no. 2, pp. 189-202. 
@article{ITA_1990__24_2_189_0,
     author = {Gaibisso, C. and Gambosi, G. and Talamo, M.},
     title = {A partially persistent data structure for the set-union problem},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {189--202},
     publisher = {EDP-Sciences},
     volume = {24},
     number = {2},
     year = {1990},
     mrnumber = {1073533},
     zbl = {0701.68021},
     language = {en},
     url = {http://www.numdam.org/item/ITA_1990__24_2_189_0/}
}
TY  - JOUR
AU  - Gaibisso, C.
AU  - Gambosi, G.
AU  - Talamo, M.
TI  - A partially persistent data structure for the set-union problem
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1990
SP  - 189
EP  - 202
VL  - 24
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1990__24_2_189_0/
LA  - en
ID  - ITA_1990__24_2_189_0
ER  - 
%0 Journal Article
%A Gaibisso, C.
%A Gambosi, G.
%A Talamo, M.
%T A partially persistent data structure for the set-union problem
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1990
%P 189-202
%V 24
%N 2
%I EDP-Sciences
%U http://www.numdam.org/item/ITA_1990__24_2_189_0/
%G en
%F ITA_1990__24_2_189_0
Gaibisso, C.; Gambosi, G.; Talamo, M. A partially persistent data structure for the set-union problem. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 24 (1990) no. 2, pp. 189-202. http://www.numdam.org/item/ITA_1990__24_2_189_0/

1. A. V. Aho, J. E. Hopcroft and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974. | MR | Zbl

2. N. Blum, On the Single Operation Worst-case Time Complexity of the Disjoint Set Union problem, Proc. 2nd Symp. on Theoretical Aspects of Computer Science, 1985. | MR | Zbl

3. B. Bollobas and I. Simon, On the Expected Behavior of Disjoint Set Union Algorithms, Proc. 17th ACM Symp. on Theory of Computing, 1985.

4. J. R. Driscoll, N. Sarnak, D. D. Sleator and R. E. Tarjan, Making Data Structures Persistent, Proc. 18th Symp. on Theory of Computing STOC, 1986.

5. M. J. Fischer, Efficiency of Equivalence Algorithms, in Complexity of Computations, R. E. MILLER and J. W. THATCHER Eds., Plenum Press, New York, 1972. | MR

6. H. N. Gabow and R. E. Tarjan, A Linear Time Algorithm for a Special case of Disjoint Set Union, Proc. 15th A.C.M. Symp. on Theory of Computing 1983.

7. B. A. Galler and M. J. Fischer, An Improved Equivalence Algorithm, Comm. ACM 7, 1964. | Zbl

8. G. Gambosi, G. F. Italiano and M. Talamo, Worst-Case Analysis of the Set Union Problem with Backtracking, to appear on "Theoretical Computer Science", 1989. | Zbl

9. J. E. Hopcroft and J. D. Ullman, Set Merging Algorithms, S.I.A.M. J. Comput., 2, 1973. | MR | Zbl

10. H. Mannila and E. Ukkonen, The Set Union Problem with Backtracking, Proc. 13th I.C.A.L.P., 1986. | MR | Zbl

11. R. E. Tarjan, Efficiency of a Good but not Linear Disjoint Set Union Algorithm, J. A.C.M., 22, 1975. | MR | Zbl

12. R. E. Tarjan, A Class of Algorithms which Require Linear Time to Mantain Disjoint Sets, J. Computer and System Sciences, 18, 1979. | MR | Zbl

13. R. E. Tarjan, Amortized Computational Complexity, S.I.A.M. J. Alg. Discr. Meth., 6, 1985. | MR | Zbl

14. R. E. Tarjan and J. Van Leeuwen, Worst-Case Analysis of Set Union Algorithms, J. A.C.M. 31, 1984. | MR | Zbl

15. J. Van Leeuwen and T. Van Der Weide, Alternative Path Compression Techniques, Techn. Rep. RUU-CS-77-3, Rijksuniversiteit Utrecht, The Netherlands.

16. J. Westbrook and R. E. Tarjan, Amortized Analysis of Algorithms for Set-Union with Backtracking, Tech. Rep. TR-103-87, Dept. of Computer Science, Princeton University, 1987.