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

Harold N. Gabow, Robert Endre Tarjan

Research output: Contribution to journalArticle

349 Scopus citations

Abstract

This paper presents 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. The algorithm executes an intermixed sequence of m union and find operations on n elements in O(m+n) time and O(n) space. This is a slight but theoretically significant improvement over the fastest known algorithm for the general problem, which runs in O(mα(m+n, n)+n) time and O(n) space, where a is a functional inverse of Ackermann's function. Used as a subroutine, the algorithm gives similar improvements in the efficiency of algorithms for solving several other problems, including two-processor scheduling, matching on convex graphs, finding nearest common ancestors off-line, testing a flow graph for reducibility, and finding two disjoint directed spanning trees. The algorithm obtains its efficiency by combining the fast algorithm for the general problem with table look-up on small sets, and requires a random access machine for its implementation. The algorithm extends to the case in which single-node additions to the union tree are allowed. The extended algorithm is useful in finding maximum cardinality matchings in nonbipartite graphs.

Original languageEnglish (US)
Pages (from-to)209-221
Number of pages13
JournalJournal of Computer and System Sciences
Volume30
Issue number2
DOIs
StatePublished - Apr 1985
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A linear-time algorithm for a special case of disjoint set union'. Together they form a unique fingerprint.

  • Cite this