On the average behavior of set merging algorithms (Extended Abstract)

ABSTRACT

In this paper we study the expected running time of a variety of algorithms that perform set merging. The set merging problem (for example, see AHU [1]) is concerned with using suitable data structures to represent partition of a set S &equil; { 1,2, .... ,n} so that a sequence of instructions of the form “x &Xgr; y”, meaning “Find the subset containing x; Find the subset containing y; Merge the two subsets if they are different.” may be carried out efficiently. Several alternative data structures for solving this problem are known, and their worse-case complexity fairly well understood [3], [4], [5], [8]. In contrast, the average behavior of even the most basic of these schemes remains an open problem [6]. It is the purpose of the present paper to determine the average behavior for several of the set merging algorithms commonly known.

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: Erdös and Rényi(1960), On the Evolution of Random Graphs, The Art of Counting by P. Erdos, 1973, M.I.T. Press.
• 3: M. Fischer(1972), Efficiency of Equivalence Algorithms, in Complexity of Computer Computations, edited by Miller and Thatcher, Plenum Press, New York 1972.
• 4: Benrard A. Galler , Michael J. Fisher, An improved equivalence algorithm, Communications of the ACM, v.7 n.5, p.301-303, May 1964 [doi>10.1145/364099.364331]
• 5: J. Hopcroft and J. Ullman(1973), Set Merging Algorithms, SIAM J. Computing, 2.
• 6: D. Knuth(1968), Fundamental Algorithms, Addison-Wesley, Sec. 2.3.3. Exercise 19.
• 7: A. Rényi(1959), Some Remarks on the Theory of Trees, Publications of the Math. Inst. of the Hung. Acad. of Sci. 4.
• 8: 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]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Algorithms