zbMATH — the first resource for mathematics

A partially persistent data structure for the set-union problem. (English) Zbl 0701.68021
Summary: We consider an extension of the well known Set-Union problem, where a search in the history of the partition is possible. A partially persistent data structure is presented which maintains a partition of an n-item set with no overhead on the worst case complexity of the ephemeral structure, i.e. it performs each Union in 0(1) time, each Find in 0(lg n) time and each search in the past in 0(lg n) time. The space complexity for such a structure is 0(n).

68P05 Data structures
68Q25 Analysis of algorithms and problem complexity
68R05 Combinatorics in computer science
Full Text: DOI EuDML
[1] 1. A. V. AHO, J. E. HOPCROFT and J. D. ULLMAN, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974. Zbl0326.68005 MR413592 · Zbl 0326.68005
[2] 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.68055 MR786866 · Zbl 0568.68055
[3] 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] 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. · Zbl 0667.68026
[5] 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] 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. · Zbl 0572.68058
[7] 7. B. A. GALLER and M. J. FISCHER, An Improved Equivalence Algorithm, Comm. ACM 7, 1964. Zbl0129.10302 · Zbl 0129.10302
[8] 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 · Zbl 0678.68035
[9] 9. J. E. HOPCROFT and J. D. ULLMAN, Set Merging Algorithms, S.I.A.M. J. Comput., 2, 1973. Zbl0253.68003 MR329310 · Zbl 0253.68003
[10] 10. H. MANNILA and E. UKKONEN, The Set Union Problem with Backtracking, Proc. 13th I.C.A.L.P., 1986. Zbl0596.68039 MR864686 · Zbl 0596.68039
[11] 11. R. E. TARJAN, Efficiency of a Good but not Linear Disjoint Set Union Algorithm, J. A.C.M., 22, 1975. Zbl0307.68029 MR458996 · Zbl 0307.68029
[12] 12. R. E. TARJAN, A Class of Algorithms which Require Linear Time to Mantain Disjoint Sets, J. Computer and System Sciences, 18, 1979. Zbl0413.68039 MR532171 · Zbl 0413.68039
[13] 13. R. E. TARJAN, Amortized Computational Complexity, S.I.A.M. J. Alg. Discr. Meth., 6, 1985. Zbl0599.68046 MR778012 · Zbl 0599.68046
[14] 14. R. E. TARJAN and J. VAN LEEUWEN, Worst-Case Analysis of Set Union Algorithms, J. A.C.M. 31, 1984. Zbl0632.68043 MR819138 · Zbl 0632.68043
[15] 15. J. VAN LEEUWEN and T. VAN DER WEIDE, Alternative Path Compression Techniques, Techn. Rep. RUU-CS-77-3, Rijksuniversiteit Utrecht, The Netherlands.
[16] 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. · 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.