A linear-time algorithm for a special case of disjoint set union

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&agr;(m+n, n)+n) time and 0(n) space, where &agr; 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.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 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.
• 3: Edsger Wybe Dijkstra, A Discipline of Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1997
• 4: J. Doyle and R.L. Rivest, "Linear expected time of a simple union-find algorithm," Inf. Proc. Letters 5, 1976, pp. 146-148.
• 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.
• 6: Harold N. Gabow, An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs, Journal of the ACM (JACM), v.23 n.2, p.221-234, April 1976 [doi>10.1145/321941.321942]
• 7: H.N. Gabow, "A linear-time recognition algorithm for interval dags," Inf. Proc. Letters 12 (1981), pp. 20-22.
• 8: Harold N. Gabow, An Almost-Linear Algorithm for Two-Processor Scheduling, Journal of the ACM (JACM), v.29 n.3, p.766-780, July 1982 [doi>10.1145/322326.322335]
• 9: John R. Gilbert , Donald J. Rose, A Separator Theorem for Chordal Graphs, Cornell University, Ithaca, NY, 1982
• 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.
• 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.
• 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.
• 13: Ellis Horowitz , Sartaj Sahni, Fundamentals of Computer Alori, W. H. Freeman & Co., New York, NY, 1978
• 14: Dov Harel , Robert Endre Tarjan, Fast algorithms for finding nearest common ancestors, SIAM Journal on Computing, v.13 n.2, p.338-355, May 1984 [doi>10.1137/0213024]
• 15: J.E. Hopcroft and J.D. Ullman, "Set merging algorithms," SIAM J. Comput. 2, 4, 1973, pp. 294-303.
• 16: D.E. Knuth and A. Schonhage, "The expected linearity of a simple equivalence algorithm," Theoretical Comp. Sci. 6 (1978), pp. 281-315.
• 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.
• 18: Thomas Lengauer , Robert Endre Tarjan, A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.121-141, July 1979 [doi>10.1145/357062.357071]
• 19: S. Micali, private communication, May 1982.
• 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.
• 21: C.H. Papadimitriou and M. Yannakakis, "Scheduling interval-ordered tasks," SIAM J, Comput. 8, 3, 1979, pp. 405-409.
• 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.
• 23: R. Sethi, "Scheduling graphs on two processors," SIAM J. Comp. 5 (1976), pp, 73-82.
• 24: R.E. Stearns and D.J. Rosenkrantz, "Table machine simulation." Proc. 10th Annual Symp. on Switching and Automata Theory, 1969, pp. 118-128.
• 25: R.E. Tarjan, "Testing flow graph reducibility," J. Comp. Sys. Sci 9 (1974), pp. 355-365.
• 26: Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
• 27: R.E. Tarjan, "Edge-disjoint spanning trees and depth-first search," Acta Informatica 6 (1976), pp. 171-185.
• 28: Robert Endre Tarjan, Applications of Path Compression on Balanced Trees, Journal of the ACM (JACM), v.26 n.4, p.690-715, Oct. 1979 [doi>10.1145/322154.322161]
• 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.
• 30: J. E. Thornton, Design of a Computer—The Control Data 6600, Scott Foresman & Co, 1970
• 31: Robert E. Tarjan , Jan van Leeuwen, Worst-case Analysis of Set Union Algorithms, Journal of the ACM (JACM), v.31 n.2, p.245-281, April 1984 [doi>10.1145/62.2160]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Set theory

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Theory