Tarjan, Robert E.; van Leeuwen, Jan Worst-case analysis of set union algorithms. (English) Zbl 0632.68043 J. Assoc. Comput. Mach. 31, 245-281 (1984). 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 Rem and advocated by Dijkstra, are slower than the best methods. Cited in 1 ReviewCited in 58 Documents MSC: 68Q25 Analysis of algorithms and problem complexity 68R99 Discrete mathematics in relation to computer science 68R10 Graph theory (including graph drawing) in computer science Keywords:equivalence algorithm; set union; inverse Ackermann function; asymptotic worst-case running time; path compression PDF BibTeX XML Cite \textit{R. E. Tarjan} and \textit{J. van Leeuwen}, J. Assoc. Comput. Mach. 31, 245--281 (1984; Zbl 0632.68043) Full Text: DOI OpenURL