×

A linear-time algorithm for a special case of disjoint set union. (English) Zbl 0572.68058

This paper presents a linear-time algorithm for the special case of the disjoint set union problem in which the structure of the unions (defined by a ”union tree”) is known in advance. The algorithm executes an intermixed sequence of m union and find operations on n elements in \(O(m+n)\) time and O(n) space. This is a slight but theoretically significant improvement over the fastest known algorighm for the general problem, which runs in \(O(m\alpha (m+n,n)+n)\) time and O(n) space, where \(\alpha\) is a functional inverse of Ackermann’s function.

MSC:

68R99 Discrete mathematics in relation to computer science
68Q25 Analysis of algorithms and problem complexity

Keywords:

union tree
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Annalysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, Mass
[2] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., On finding lowest common ancestors in trees, SIAM J. Comput., 5, 115-132 (1976) · Zbl 0325.68018
[3] Dijkstra, E. W., A Discipline of Programming (1976), Prentice-Hall: Prentice-Hall Englewood Cliffs N.J · Zbl 0286.00013
[4] Doyle, J.; Rivest, R. L., Linear expected time of a simple union-find algorithm, Inform. Process. Lett., 5, 146-148 (1976) · Zbl 0345.68024
[5] Frederickson, G. N., Scheduling unit-time tasks with integer release times and deadlines, Inform. Process. Lett., 16, 171-173 (1983) · Zbl 0508.68023
[6] Gabow, H. N., An efficient implementation of Edmonds’ algorithm for maximum matching on graphs, J. Assoc. Comput. Mach., 23, 221-234 (1976) · Zbl 0327.05121
[7] Gabow, H. N., A linear-time recognition algorithm for interval dags, Inform. Process. Lett., 12, 20-22 (1981) · Zbl 0454.68011
[8] Gabow, H. N., An almost-linear algorithm for two-processor scheduling, J. Assoc. Comput. Mach., 29, 766-780 (1982) · Zbl 0485.68034
[9] Gabow, H. N.; Tarjan, R. E., A linear-time algorithm for a special case of disjoint set union, (Proc. 15th Annual ACM Sympos. on Theory of Computing (1983)), 246-251
[10] Harel, D., A linear time algorithm for the least common ancestors problem, (Proc. 21st Annual Sympos. on Found. of Comput. Sci. (1980)), 308-319
[11] Harel, D.; Tarjan, R. E., Fast algorithms for finding nearest common ancestors, SIAM J. Comput., 13, 338-355 (1984) · Zbl 0535.68022
[12] Havens, B., Experiments on an Asymptotically Optimum, Special Purpose Set Merging Algorithm, (M. S. thesis (1983), Department of Computer Science, University of Colorado: Department of Computer Science, University of Colorado Boulder, Clo)
[13] Hopcroft, J. E.; Ullman, J. D., Set merging algorithms, SIAM J. Comput., 2, 294-303 (1973) · Zbl 0253.68003
[14] Horowitz, E.; Sahni, S., Fundamentals of Computer Algorithms (1978), Computer Science: Computer Science Potomac, Md · Zbl 0442.68022
[15] H. Imai and T. Asano, Efficient algorithms for geometric graph search problems, J. Algorithms, to appear.; H. Imai and T. Asano, Efficient algorithms for geometric graph search problems, J. Algorithms, to appear. · Zbl 0591.68068
[16] Imai, H.; Asano, T., Dynamic segment intersection search with applications, (Proc. 25th Annual IEEE Sympos. on Found. of Comput. Sci. (1984)), 393-402
[17] Knuth, D. E.; Schönhage, A., The expected linearity of a simple equivalence algorithm, Theoret. Comput. Sci., 6, 281-315 (1978) · Zbl 0377.68024
[18] Lengauer, T.; Tarjan, R. E., A fast algorithm for finding dominators in a flowgraph, ACM Trans. Programming Lang. Systems, 1, 121-141 (1979) · Zbl 0449.68024
[19] Lipski, W.; Preparata, F., Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems, Acta Inform., 15, 329-346 (1981) · Zbl 0445.68052
[20] Lipski, W., An \(O(n\) log \(n)\) Manhattan path algorithm, Inform. Process. Lett., 19, 99-102 (1984) · Zbl 0542.68052
[21] S. Micali, Private communication, May 1982.; S. Micali, Private communication, May 1982.
[22] Micali, S.; Vazirani, V. V., An
((O(√|V\)| · |E\)|) algorithm for finding maximum matching in general graphs, (Proc. 21st Annual IEEE Sympos. on Found. of Comput. Sci. (1980)), 17-27
[23] Papadimitriou, C. H.; Yannakakis, M., Scheduling interval-ordered tasks, SIAM J. Comput., 8, 405-409 (1979) · Zbl 0421.68040
[24] Preparata, F. P.; Lipski, W., Three layers are enough, (Proc. 23rd Annual IEEE Sympos. on Found. of Comput. Sci. (1982)), 350-357
[25] Sethi, R., Scheduling graphs on two processors, SIAM J. Comput., 5, 73-82 (1976) · Zbl 0328.68057
[26] Tarjan, R. E., Testing flow graph reducibility, J. Comput. System Sci., 8, 355-365 (1974) · Zbl 0315.68018
[27] Tarjan, R. E., Efficiency of a good but not linear set union algorithm, J. Assoc. Comput. Mach., 22, 215-225 (1975) · Zbl 0307.68029
[28] Tarjan, R. E., Edge-disjoint spanning trees and depth-first search, Acta Inform., 6, 171-185 (1976) · Zbl 0307.05104
[29] Tarjan, R. E., Applications of path compression on balanced trees, J. Assoc. Comput. Mach., 26, No.4, 690-715 (1979) · Zbl 0413.68063
[30] Tarjan, R. E., A class of algorithms which require non-linear time to maintain disjoint sets, J. Comput. System-Sci., 18, 110-127 (1979) · Zbl 0413.68039
[31] Tarjan, R. E.; Van Leeuwen, J., Worst-case analysis of set union algorithms, J. Assoc. Comput. Mach., 31, 245-281 (1984) · Zbl 0632.68043
[32] Harel, D., A linear algorithm for finding dominators in flow graphs and related problems, (Proc. 17th Annual ACM Sympos. on Theory of Computing (1985)), to appear
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.