A partially persistent data structure for the set-union problem
Gaibisso, C. ; Gambosi, G. ; Talamo, M.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 24 (1990), p. 189-202 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1990-01-01
@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},
     volume = {24},
     year = {1990},
     pages = {189-202},
     mrnumber = {1073533},
     zbl = {0701.68021},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 189-202. http://gdmltest.u-ga.fr/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 413592 | Zbl 0326.68005

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 786866 | Zbl 0568.68055

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 395316

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 0129.10302

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 0678.68035

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

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

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

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

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

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

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.