A class of algorithms which require nonlinear time to maintain disjoint sets. (English) Zbl 0413.68039


68Q25 Analysis of algorithms and problem complexity
68W99 Algorithms in computer science
Full Text: DOI


[1] Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, Mass · Zbl 0286.68029
[2] Borodin, A.; Munro, I., The computational complexity of algebraic and numeric problems, (1975), Elsevier New York · Zbl 0404.68049
[3] Doyle, J.; Rivest, R.L., Linear expected time of a simple union-find algorithm, Inform. processing lett., 5, 146-148, (1976) · Zbl 0345.68024
[4] Fischer, M.J., Efficiency of equivalence algorithms, (), 153-168
[5] Galler, B.A.; Fischer, M.J., An improved equivalence algorithm, Comm. ACM, 7, 301-303, (1964) · Zbl 0129.10302
[6] Hopcroft, J.E.; Ullman, J.D., Set merging algorithms, SIAM J. comput., 2, 294-303, (1973) · Zbl 0253.68003
[7] Jazayeri, M.; Ogden, W.F.; Rounds, W.C., The intrinsically exponential complexity of the circularity problem for attribute grammars, Comm. ACM, 18, 697-706, (1975) · Zbl 0318.68051
[8] Knuth, D.E., ()
[9] Knuth, D.E., ()
[10] Knuth, D.E.; Schönhage, A., The expected linearity of a simple equivalence algorithm, () · Zbl 0377.68024
[11] Kolmogorov, A.N., On the notion of algorithm, Uspehi mat. nauk., 8, 175-176, (1953)
[12] Kolmogorov, A.N.; Uspenskii, V.A.; Kolmogorov, A.N.; Uspenskii, V.A., On the definition of an algorithm, Uspehi mat. nauk., Amer. math. soc. transl., 29, 217-245, (1963), English translation · Zbl 0128.01302
[13] Meyer, A.R.; Stockmeyer, L.J., The equivalence problem for regular expressions with squaring requires exponential space, (), 125-129
[14] Rabin, M.J.; Fischer, M.J., Super-exponential complexity of Presburger arithmetic, (), 27-41
[15] Rivest, R.; Vuillemin, J., On recognizing graph properties from adjacency matrices, Theoret. comput. sci., 3, 371-384, (1976) · Zbl 0358.68079
[16] Schönhage, A., Real-time simulation of multidimensional Turing machines by storage modification machines, () · Zbl 0454.68034
[17] Tartan, R.E., Efficiency of a good but not linear disjoint set union algorithm, J. assoc. comput. Mach., 22, 215-225, (1975)
[18] Tartan, R.E., Applications of path compression on balanced trees, ()
[19] Tartan, R.E., Solving path problems on directed graphs, ()
[20] Yao, A.C., On the average behavior of set merging algorithms, (), 192-195
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.