Andrew Chi-chih Yao
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 = { 1,2, .... ,n} so that a sequence of instructions of the form “x Ξ 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.
- 1.Aho, Hopcroft and Ullman(1974), The Desigh and Analysis of Computer Algorithms, chapter 4. Addison-Wesley. Google Scholar
Digital Library
- 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.Google Scholar
- 3.M. Fischer(1972), Efficiency of Equivalence Algorithms, in Complexity of Computer Computations, edited by Miller and Thatcher, Plenum Press, New York 1972.Google Scholar
- 4.B. Galler and M. Fischer(1964), An Improved Equivalence Algorithm, Comm. ACM 7. Google ScholarDigital Library
- 5.J. Hopcroft and J. Ullman(1973), Set Merging Algorithms, SIAM J. Computing, 2.Google Scholar
- 6.D. Knuth(1968), Fundamental Algorithms, Addison-Wesley, Sec. 2.3.3. Exercise 19.Google Scholar
- 7.A. Rényi(1959), Some Remarks on the Theory of Trees, Publications of the Math. Inst. of the Hung. Acad. of Sci. 4.Google Scholar
- 8.R. Tarjan(1975), On the Efficiency of a Good But not Linear Set Merging Algorithm, JACM 22. Google ScholarDigital Library
Index Terms
- On the average behavior of set merging algorithms (Extended Abstract)
Recommendations
Modeling Vehicle Merging Behavior in Work Zone Merging Areas During the Merging Implementation Period
Using the classification and regression tree (CART) method, this study aims to model the vehicle merging behavior at work zone merging areas during the merging implementation period. Hereafter, the merging implementation period is defined as the period ...
Declarative belief set merging using merging plans
PADL'11: Proceedings of the 13th international conference on Practical aspects of declarative languagesWe present a declarative framework for belief set merging tasks over (possibly heterogeneous) knowledge bases, where belief sets are sets of literals. The framework is designed generically for flexible deployment to a range of applications, and allows ...
Set Merging Algorithms
This paper considers the problem of merging sets formed from a total of n items in such a way that at any time, the name of a set containing a given item can be ascertained. Two algorithms using different data structures are discussed. The execution times ...
Comments