Worst-Case Analysis of Set Union Algorithms

Robert E. Tarjan, Jan van Leeuwen

Research output: Contribution to journalArticle

252 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)245-281
Number of pages37
JournalJournal of the ACM (JACM)
Volume31
Issue number2
DOIs
StatePublished - Mar 30 1984
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Keywords

  • Equivalence algorithm
  • inverse Aekermann's function
  • set union

Fingerprint Dive into the research topics of 'Worst-Case Analysis of Set Union Algorithms'. Together they form a unique fingerprint.

  • Cite this