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

DOI10.1016/0022-0000(85)90014-5zbMath0572.68058MaRDI QIDQ1062461

Harold N. Gabow, Robert Endre Tarjan

Publication date: 1985

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(85)90014-5

zbMATH Keywords

union tree

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R99: Discrete mathematics in relation to computer science

Related Items

Processing an Offline Insertion-Query Sequence with Applications, Minimizing the density of terminal assignments in layout design, The level ancestor problem simplified, Two linear time Union--Find strategies for image processing, A faster algorithm for the two-center decision problem, Complete bound consistency for the global cardinality constraint, Sequential and parallel algorithms for the NCA problem on pure pointer machines, Efficient algorithms for robustness in resource allocation and scheduling problems, Dynamic fractional cascading, Edge-disjoint paths in a grid bounded by two nested rectangles, Minimizing the number of tardy job units under release time constraints, An O\((n\log n)\) version of the Averbakh-Berman algorithm for the robust median of a tree, Efficient algorithms for two generalized 2-median problems and the group median problem on trees, A linear time \(\frac{5}{3}\)-approximation for the minimum strongly-connected spanning subgraph problem, Matching subsequences in trees, Visibility of disjoint polygons, An augmenting path algorithm for linear matroid parity, The general maximum matching algorithm of Micali and Vazirani, Computing the bump number with techniques from two-processor scheduling, A matroid algorithm and its application to the efficient solution of two optimization problems on graphs, Algorithms for multicommodity flows in planar graphs, Unifications, deunifications, and their complexity, Forests, frames, and games: Algorithms for matroid sums and applications, Efficient parallel algorithms for path problems in directed graphs, Farthest neighbors, maximum spanning trees and related problems in higher dimensions, Minimizing the sum of diameters efficiently, A fast bipartite network flow algorithm for selective assembly, Efficient Union-Find for planar graphs and other sparse graph classes, Optimal binary trees with order constraints, Modular decomposition and transitive orientation, A software package of algorithms and heuristics for disjoint paths in \textit{Pla}nar \textit{Net}works, A linear time algorithm for unique Horn satisfiability, A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm, Minimizing the weighted number of tardy task units, A lower bound on the single-operation worst-case time complexity of the union-find problem on intervals, A linear-time construction of the relative neighborhood graph from the Delaunay triangulation, A constant update time finger search tree, Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits, Parallel maximum independent set in convex bipartite graphs, A note on finding compact sets in graphs represented by an adjacency list, Planar stage graphs: Characterizations and applications, The maximum deviation just-in-time scheduling problem., Recognizing quasi-triangulated graphs., Single backup table schemes for shortest-path routing, Topologically sweeping visibility complexes via pseudotriangulations, A linear-time algorithm for edge-disjoint paths in planar graphs, An optimal algorithm for reporting visible rectangles, Dynamic nested brackets, On the \(k\)-coloring of intervals, Permuting matrices to avoid forbidden submatrices, An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications, Scheduling tree-like task systems with non-uniform deadlines subject to unit-length communication delays, Multicommodity flows in cycle graphs, Path problems in skew-symmetric graphs, Linear time algorithms for graph search and connectivity determination on complement graphs., An optimal time and minimal space algorithm for rectangle intersection problems, Optimal parallel algorithm for shortest-paths problem on interval graphs, A partially persistent data structure for the set-union problem, Amortized Computational Complexity, Inferring regular languages by merging nonterminals

Cites Work