Harold N. Gabow
Robert Endre Tarjan
ABSTRACT
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 0(m+n) time and 0(n) space. This is a slight but theoretically significant improvement over the fastest known algorithm for the general problem, which runs in 0(mα(m+n, n)+n) time and 0(n) space, where α is a functional inverse of Ackermann's function. Used as a subroutine, the algorithm gives similar improvements in the efficiency of algorithms for solving a number of other problems, including two-processor scheduling, the off-line min problem, matching on convex graphs, finding nearest common ancestors off-line, testing a flow graph for reducibility, and finding two disjoint directed spanning trees. The algorithm obtains its efficiency by combining a fast algorithm for the general problem with table look-up on small sets, and requires a random access machine for its implementation. The algorithm extends to the case in which single-node additions to the union tree are allowed. The extended algorithm is useful in finding maximum cardinality matchings on nonbipartite graphs.
- 1.A.V. Aho, J.E. Hopcroft, J.D. Ullman The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass., 1974. Google Scholar
Digital Library
- 2.A.V. Aho, J.E. Hopcroft, J.D. Ullman, "On finding lowest common ancestors in trees," SIAM J. Comp. 5 (1976), pp. 115-132.Google ScholarDigital Library
- 3.E.W. Dijkstra, A Discipline of Programming, Prentice-Hall, Englewood Cliffs, New Jersey, 1976. Google ScholarDigital Library
- 4.J. Doyle and R.L. Rivest, "Linear expected time of a simple union-find algorithm," Inf. Proc. Letters 5, 1976, pp. 146-148.Google ScholarCross Ref
- 5.G.N. Frederickson, "Scheduling unit-time tasks with integer release times and deadlines," Tech. Rept. CS-81-27, Dept. of Computer Sci., Penn. State Univ., University Park, PA, 1982.Google Scholar
- 6.H.N. Gabow, "An efficient implementation of Edmonds' algorithm for maximum matching on graphs," J. ACM 23 (1976) pp. 221-234. Google ScholarDigital Library
- 7.H.N. Gabow, "A linear-time recognition algorithm for interval dags," Inf. Proc. Letters 12 (1981), pp. 20-22.Google ScholarCross Ref
- 8.H.N. Gabow, "An almost-linear algorithm for two-processor scheduling," J. ACM, 29, 3 (1982), pp. 766-780. Google ScholarDigital Library
- 9.J.R. Gilbert and D.J. Rose, "A separator theorem for chordal graphs," Tech. Rept. TR 82-523, Dept. of Comp. Sci., Cornell Univ., Ithaca, New York, 1982. Google ScholarDigital Library
- 10.H.N. Gabow and R.E. Tarjan, "A linear-time algorithm for a special case of disjoint set union," Bell Laboratories Report, July 1982.Google Scholar
- 11.D. Harel, "A linear time algorithm for the least common ancestors problem," Proc. 21st Annual Symp. on Found. Comp. Sci. (1980), pp. 308-319.Google Scholar
- 12.B. Havens, "Experiments on an asymptotically optimum, special purpose set merging algorithm," M.S. Thesis, Dept. of Computer Sci., Univ. of Colorado, Boulder, CO, 1983.Google Scholar
- 13.E. Horowitz, and S. Sahni, Fundamentals of Computer Algorithms, Computer Science Press, Potomac, MD, 1978. Google ScholarDigital Library
- 14.D. Harel, R.E. Tarjan, "Fast algorithms for finding nearest common ancestors," SIAM J. Comput., submitted. Google ScholarDigital Library
- 15.J.E. Hopcroft and J.D. Ullman, "Set merging algorithms," SIAM J. Comput. 2, 4, 1973, pp. 294-303.Google ScholarDigital Library
- 16.D.E. Knuth and A. Schonhage, "The expected linearity of a simple equivalence algorithm," Theoretical Comp. Sci. 6 (1978), pp. 281-315.Google ScholarCross Ref
- 17.W. Lipski, Jr. and F.P. Preparata, "Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems," Acta Informatica 15 (1981), pp. 329-346.Google ScholarDigital Library
- 18.T. Lengauer and R.E. Tarjan, "A fast algorithm for finding dominators in a flowgraph," ACM Trans. on Prog. Lang. and Systems 1, 1, 1979, pp. 121-141. Google ScholarDigital Library
- 19.S. Micali, private communication, May 1982.Google Scholar
- 20.S. Micali, and V.V. Vazirani. "An 0(@@@@ E) algorithm for finding maximum matching in general graphs," Proc. 21st Annual Symp. on Found. of Comp. Sci. (1980), pp. 17-27.Google Scholar
- 21.C.H. Papadimitriou and M. Yannakakis, "Scheduling interval-ordered tasks," SIAM J, Comput. 8, 3, 1979, pp. 405-409.Google ScholarDigital Library
- 22.F.P. Preparata and W. Lipski Jr., "Three layers are enough," Proc. 23rd Annual Symp. on Foundations of Comp. Sci., 1982, pp. 350-357. Also personal communication, F.P. Preparata.Google ScholarDigital Library
- 23.R. Sethi, "Scheduling graphs on two processors," SIAM J. Comp. 5 (1976), pp, 73-82.Google ScholarDigital Library
- 24.R.E. Stearns and D.J. Rosenkrantz, "Table machine simulation." Proc. 10th Annual Symp. on Switching and Automata Theory, 1969, pp. 118-128.Google ScholarDigital Library
- 25.R.E. Tarjan, "Testing flow graph reducibility," J. Comp. Sys. Sci 9 (1974), pp. 355-365.Google ScholarDigital Library
- 26.R.E. Tarjan, "Efficiency of a good but not linear set union algorithm," J. ACM 22 (1975), pp. 215-225. Google ScholarDigital Library
- 27.R.E. Tarjan, "Edge-disjoint spanning trees and depth-first search," Acta Informatica 6 (1976), pp. 171-185.Google ScholarDigital Library
- 28.R.E. Tarjan, "Applications of path compression on balanced trees," J. ACM 26, 4 (1979), pp. 690-715. Google ScholarDigital Library
- 29.R.E. Tarjan, "A class of algorithms which require non-linear time to maintain disjoint sets," J. Comp. Sys. Sci. 18 (1979), pp. 110-127.Google ScholarCross Ref
- 30.J.E. Thornton, Design of a computer: The Control Data 6600, Scott, Foresman and Co., Glenview, Illinois, 1970. Google ScholarDigital Library
- 31.R.E. Tarjan, J. van Leeuwen, "Worst-case analysis of set union algorithms," J. ACM, submitted. Google ScholarDigital Library
Index Terms
- A linear-time algorithm for a special case of disjoint set union
Recommendations
On the expected behavior of disjoint set union algorithms
STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computingWe show that the expected time of the Weighted Quickfind (QFW) disjoint set union and find algorithm to perform (n - 1) randomly chosen unions is cn + o(n/log n), where c = 2.0847 …. This implies, through an observation of Tarjan and Van Leeuwen, linear ...
On the Equitable Choosability of the Disjoint Union of Stars
AbstractEquitable k-choosability is a list analogue of equitable k-coloring that was introduced by Kostochka et al. (J Graph Theory 44:166–177, 2003). It is known that if vertex disjoint graphs and are equitably k-choosable, the disjoint union of ...
A linear-time algorithm for constructing a circular visibility diagram
To computer circular visibility inside a simple polygon, circular arcs that emanate from a given interior point are classified with respect to the edges of the polygon they first intersect. Representing these sets of circular arcs by their centers ...
Comments