March 30, 1984Open Access

Worst-case Analysis of Set Union Algorithms

Key Points

Key points are not available for this paper at this time.

Abstract

This paper analyzes the asymptotic worst-case running time of a number of variants of the well-known method of path compression for maintaining a collection of disjoint sets under union. We show that two one-pass methods proposed by van Leeuwen and van der Weide are asymptotically optimal, whereas several other methods, including one proposed by Rein and advocated by Dijkstra, are slower than the best methods.

Bookmark

View Full Paper

Cite This Study

Tarjan et al. (Fri,) studied this question.

synapsesocial.com/papers/6a1eb2636e6b94f521a4350e https://doi.org/https://doi.org/10.1145/62.2160

Also Consider

Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context:

1A complement to Tarjan's result about the lower bound on the complexity of the set union problem1980 · 23 citations
2Applications of Path Compression on Balanced Trees1979 · 300 citations
3A class of algorithms which require nonlinear time to maintain disjoint sets1979 · 266 citations
4A new data structure for the union-find problem1979 · 4 citations
5A linear-time algorithm for a special case of disjoint set union1983 · 171 citations

Bookmark

View Full Paper