A partially persistent data structure for the set-union problem
C. Gaibisso; G. Gambosi; M. Talamo
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1990)
- Volume: 24, Issue: 2, page 189-202
- ISSN: 0988-3754
Access Full Article
top
How to cite
topGaibisso, C., Gambosi, G., and Talamo, M.. "A partially persistent data structure for the set-union problem." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 24.2 (1990): 189-202. <http://eudml.org/doc/92355>.
@article{Gaibisso1990,
author = {Gaibisso, C., Gambosi, G., Talamo, M.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {Set-Union problem; data structure; worst case complexity},
language = {eng},
number = {2},
pages = {189-202},
publisher = {EDP-Sciences},
title = {A partially persistent data structure for the set-union problem},
url = {http://eudml.org/doc/92355},
volume = {24},
year = {1990},
}
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
PB - EDP-Sciences
VL - 24
IS - 2
SP - 189
EP - 202
LA - eng
KW - Set-Union problem; data structure; worst case complexity
UR - http://eudml.org/doc/92355
ER -
References
top- 1. A. V. AHO, J. E. HOPCROFT and J. D. ULLMAN, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974. Zbl0326.68005MR413592
- 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. Zbl0568.68055MR786866
- 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. Zbl0667.68026
- 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. MR395316
- 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. Zbl0572.68058
- 7. B. A. GALLER and M. J. FISCHER, An Improved Equivalence Algorithm, Comm. ACM 7, 1964. Zbl0129.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. Zbl0678.68035
- 9. J. E. HOPCROFT and J. D. ULLMAN, Set Merging Algorithms, S.I.A.M. J. Comput., 2, 1973. Zbl0253.68003MR329310
- 10. H. MANNILA and E. UKKONEN, The Set Union Problem with Backtracking, Proc. 13th I.C.A.L.P., 1986. Zbl0596.68039MR864686
- 11. R. E. TARJAN, Efficiency of a Good but not Linear Disjoint Set Union Algorithm, J. A.C.M., 22, 1975. Zbl0307.68029MR458996
- 12. R. E. TARJAN, A Class of Algorithms which Require Linear Time to Mantain Disjoint Sets, J. Computer and System Sciences, 18, 1979. Zbl0413.68039MR532171
- 13. R. E. TARJAN, Amortized Computational Complexity, S.I.A.M. J. Alg. Discr. Meth., 6, 1985. Zbl0599.68046MR778012
- 14. R. E. TARJAN and J. VAN LEEUWEN, Worst-Case Analysis of Set Union Algorithms, J. A.C.M. 31, 1984. Zbl0632.68043MR819138
- 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. Zbl0679.68039
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.