1983/01/01 by Harold N. Gabow, Robert E. Tarjan · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Optimization and Search Problems #Interconnection Networks and Systems #Disjoint sets #Ackermann function #Algorithm #Disjoint union (topology) #Computer science #Floyd–Warshall algorithm #Time complexity #Matching (statistics) #Cardinality (data modeling) #Binary logarithm #Mathematics #Combinatorics #Discrete mathematics #Graph #Shortest path problem #Inverse #Dijkstra's algorithm
paper · doi:10.1145/800061.808753
openalex publication_date 1983/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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 0(m+n) time and 0(n) space. This is a slight but theoretically significant improvement over the fastest known algorithm for the general problem, which runs in 0(ma(m+n, n)+n) time and 0(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 a number of other problems, including two-processor scheduling, the off-line min problem, 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 a 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 on nonbipartite graphs.