# Efficiency of a Good But Not Linear Set Union Algorithm

@article{Tarjan1975EfficiencyOA, title={Efficiency of a Good But Not Linear Set Union Algorithm}, author={Robert E. Tarjan}, journal={J. ACM}, year={1975}, volume={22}, pages={215-225} }

TWO types of instructmns for mampulating a family of disjoint sets which partitmn a umverse of n elements are considered FIND(x) computes the name of the (unique) set containing element x UNION(A, B, C) combines sets A and B into a new set named C. A known algorithm for implementing sequences of these mstructmns is examined It is shown that, if t(m, n) as the maximum time reqmred by a sequence of m > n FINDs and n -- 1 intermixed UNIONs, then kima(m, n) _~ t(m, n) < k:ma(m, n) for some positive… Expand

#### Figures and Topics from this paper

#### 1,382 Citations

Some Observations on Equivalence Handling Methods

- Mathematics, Computer Science
- IEEE Transactions on Computers
- 1981

It is shown that certain modifications to the UNION operation that are convenient in some applications do not affect the running time complexity, and that under appropriate input restrictions, UNION and FIND can be made to run in linear time. Expand

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

- Mathematics, Computer Science
- STOC
- 1983

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, which gives similar improvements in the efficiency of algorithms for solving a number of other problems. Expand

Experiments on Union-Find Algorithms for the Disjoint-Set Data Structure

- Computer Science
- SEA
- 2010

An extensive experimental study comparing the time required to execute 55 variations of Union-Find algorithms shows that a somewhat forgotten simple algorithm developed by Rem in 1976 is the fastest, in spite of the fact that its worst-case time complexity is inferior to that of the commonly accepted “best” algorithms. Expand

A Linear-Time Algorithm for a Special Case of Disjoint Set Union

- Mathematics, Computer Science
- J. Comput. Syst. Sci.
- 1985

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 that is useful in finding maximum cardinality matchings in nonbipartite graphs. Expand

Lower Bounds for Selection in X + Y and Other Multisets

- Mathematics, Computer Science
- JACM
- 1978

A lower bound of f~(max(n, K 1/2 log K) is given for selecting the Kth element in X + X, and thus in X and Y, for K selecting the first through the median element Selection of gaps, that is, consecutive differences in a sorted order, is shown to be f ~(n log n) for all K. Expand

A simple and efficient Union-Find-Delete algorithm

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 2011

This note presents a conceptual and technical simplification of the Union-Find algorithm, which has the same theoretical efficiency, and is probably more attractive in practice. Expand

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

- Computer Science
- STOC '76
- 1976

The expected running time of a variety of algorithms that perform set merging is studied to determine the average behavior for several of the set merging algorithms commonly known. Expand

Union-Find with Constant Time Deletions

- Computer Science, Mathematics
- ACM Trans. Algorithms
- 2014

A relatively simple modification of the classical union-find data structure that supports delete, as well as makeset and union operations, in constant worst-case time, while still supporting find operations in O(log n) worst- case time and O(α⌈ M/N⌉ (n)) amortized time is presented. Expand

Linear Expected Time of a Simple Union-Find Algorithm

- Mathematics, Computer Science
- Inf. Process. Lett.
- 1976

This paper presents an analysis of a simple tree-structured disjoint set Union-Find algorithm, and shows that this algorithm requires between n and 2n steps on the average to execute a sequence of n… Expand

Compressing Trees with a Sledgehammer

- Computer Science
- 2016

This thesis provides a unified framework for the analysis of the compressed tree method and a meta-theorem that proves an inverse-Ackermann-type bound for a class of algorithms. Expand

#### References

SHOWING 1-10 OF 28 REFERENCES

Set Merging Algorithms

- Mathematics, Computer Science
- SIAM J. Comput.
- 1973

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… Expand

On finding lowest common ancestors in trees

- Computer Science, Mathematics
- STOC
- 1973

The first on line algorithm is applied to a problem in code optimization, that of computing immediate dominators in a reducible flow graph and it is shown how this computation can be performed in O(n log n) steps. Expand

Efficiency of Equivalence Algorithms

- Mathematics, Computer Science
- Complexity of Computer Computations
- 1972

The equivalence problem is to determine the finest partition on a set that is consistent with a sequence of assertions of the form “x ≡ y”. A strategy for doing this on a computer processes the… Expand

Finding Dominators in Directed Graphs

- Mathematics, Computer Science
- SIAM J. Comput.
- 1974

This paper describes an algorithm for finding dominators in an arbitrary directed graph. The algorithm uses depth-first search and efficient algorithms for computing disjoint set unions and… Expand

An improved equivalence algorithm

- Mathematics, Computer Science
- CACM
- 1964

An algorithm for assigning storage on the basis of EQUIVALENCE, DIMENSION and COMMON declarations is presented, and has reduced computation time by 40 percent over a previously published algorithm. Expand

Testing flow graph reducibility

- Mathematics, Computer Science
- STOC
- 1973

An algorithm for testing whether a flow graph is reducible is described, which uses depth-first search to reveal the structure of the flow graph and a good method for computing disjoint set unions to determine reducibility from the search information. Expand

Computing minimum spanning trees efficiently

- Computer Science, Mathematics
- ACM Annual Conference
- 1972

Modifications to both Prim's and Kruskal's Algorithms are introduced which give significant improvements for the complete range of sparseness, and a dramatic reduction in execution time can be obtained for sparse networks when the network under consideration is sparse. Expand

An algorithm for equivalence declarations

- Computer Science
- CACM
- 1961

Many algebraic translators provide the programmer with a limited ability to allocate storage, but there are situations in which one wishes to make certain vectors and arrays contiguous, coincident, or overlapping. Expand

Selected combinatorial research problems.

- Mathematics
- 1972

Thirty-seven research problems are described, covering a wide range of combinatorial topics. Unlike Hilbert''s problems, most of these are not especially famous and they might be "do-able" in the… Expand

The Art of Computer Programming, Volume I: Fundamental Algorithms, 2nd Edition

- Computer Science
- 1968

A container closure assembly for maintaining a sterile sealed container is provided having a ferrule having a top annular portion and a depending skirt portion for securing a resilient stopper for… Expand