The disjoint set class - Data Structures and Problem Solving Using Java - page 926

4. N. Blum, “On the Single-Operation Worst-Case Time Complexity of the
Disjoint Set Union Problem,” SIAM Journal on Computing 15 (1986),
1021-1024.
5. B. Bollobas and I. Simon, “Probabilistic Analysis of Disjoint Set Union
Algorithms,” SIAM Journal on Computing 22 (1993), 1053-1086.
6. J. Doyle and R. L. Rivest, “Linear Expected Time of a Simple Union Find
Algorithm,” Information Processing Letters 5 (1976), 146-148.
7. H. N. Gabow and R. E. Tarjan, “A Linear-Time Algorithm for a Special
Case of Disjoint Set Union,” Journal of Computer and System Sciences
30 (1985), 209-221.
8. B. A. Galler and M. J. Fischer, “An Improved Equivalence Algorithm,”
Communications of the ACM 7 (1964), 301-303.
9. J. E. Hopcroft and J. D. Ullman, “Set Merging Algorithms,” SIAM Jour-
nal on Computing 2 (1973), 294-303.
10. D. E. Knuth and A. Schonage, “The Expected Linearity of a Simple
Equivalence Algorithm,” Theoretical Computer Science 6 (1978),

281-315.
11. J. B. Kruskal, Jr., “On the Shortest Spanning Subtree of a Graph and the
Traveling Salesman Problem,” Proceedings of the American Mathemati-
cal Society 7 (1956), 48-50.
12. R. C. Prim, “Shortest Connection Networks and Some Generalizations,”
Bell System Technical Journal 36 (1957), 1389-1401.
13. R. E. Tarjan, “Efficiency of a Good but Not Linear Set Union Algorithm,”
Journal of the ACM 22 (1975), 215-225.
14. R. E. Tarjan, “A Class of Algorithms Which Require Nonlinear Time to
Maintain Disjoint Sets,” Journal of Computer and System Sciences 18
(1979), 110-127.
15. R. E. Tarjan, “Applications of Path Compression on Balanced Trees,”
Journal of the ACM 26 (1979), 690-715.
16. R. E. Tarjan and J. van Leeuwen, “Worst Case Analysis of Set Union
Algorithms,” Journal of the ACM 31 (1984), 245-281.

A. C. Yao, “On the Average Behavior of Set Merging Algorithms,” Pro-
ceedings of the Eighth Annual ACM Symposium on the Theory of Compu-
tation (1976), 192-195.

17.