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

DOI10.1016/0022-0000(85)90014-5zbMath0572.68058OpenAlexW2028503265MaRDI 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

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Related Items

Sequential and parallel algorithms for the NCA problem on pure pointer machines ⋮ Efficient algorithms for robustness in resource allocation and scheduling problems ⋮ Efficiently computing runs on a trie ⋮ Strong articulation points and strong bridges in large scale graphs ⋮ 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 note on scheduling multiprocessor tasks with precedence constraints on parallel processors ⋮ A simple linear algorithm for the edge-disjoint $(s, t)$-paths problem in undirected planar graphs ⋮ Dynamic nested brackets ⋮ Optimal on-line decremental connectivity in trees ⋮ Visibility of disjoint polygons ⋮ A constant update time finger search tree ⋮ An augmenting path algorithm for linear matroid parity ⋮ Algorithms for separable convex optimization with linear ascending constraints ⋮ Path-based depth-first search for strong and biconnected components ⋮ Gallai-Edmonds decomposition as a pruning technique ⋮ On the $k$-coloring of intervals ⋮ Permuting matrices to avoid forbidden submatrices ⋮ Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits ⋮ Parallel maximum independent set in convex bipartite graphs ⋮ 2-vertex connectivity in directed graphs ⋮ A note on finding compact sets in graphs represented by an adjacency list ⋮ Approximate generalized matching: $f$-matchings and $f$-edge covers ⋮ Dynamic matchings in left vertex weighted convex bipartite graphs ⋮ An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications ⋮ 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 ⋮ The level ancestor problem simplified ⋮ Algorithms for multicommodity flows in planar graphs ⋮ A MinCumulative resource constraint ⋮ Sparse certificates for 2-connectivity in directed graphs ⋮ Algorithms for interval structures with applications ⋮ Finding dominators via disjoint set union ⋮ Planar stage graphs: Characterizations and applications ⋮ A fast algorithm for multiplying min-sum permutations ⋮ Power domination in circular-arc graphs ⋮ Good spanning trees in graph drawing ⋮ Linear-time recognition of Helly circular-arc models and graphs ⋮ Efficient algorithms for shortest partial seeds in words ⋮ Dynamic fractional cascading ⋮ An SPQR-tree-like embedding representation for upward planarity ⋮ Finding strong bridges and strong articulation points in linear time ⋮ Edge-disjoint paths in a grid bounded by two nested rectangles ⋮ The power of linear-time data reduction for maximum matching ⋮ Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph ⋮ The maximum deviation just-in-time scheduling problem. ⋮ Max-coloring paths: tight bounds and extensions ⋮ Mobile versus point guards ⋮ 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 ⋮ Recognizing quasi-triangulated graphs. ⋮ Unifications, deunifications, and their complexity ⋮ Scheduling tree-like task systems with non-uniform deadlines subject to unit-length communication delays ⋮ A model for minimizing active processor time ⋮ Dulmage-Mendelsohn canonical decomposition as a generic pruning technique ⋮ Weighted matching as a generic pruning technique applied to optimization constraints ⋮ A simplified algorithm computing all $s-t$ bridges and articulation points ⋮ Forests, frames, and games: Algorithms for matroid sums and applications ⋮ Efficient parallel algorithms for path problems in directed graphs ⋮ Two linear time Union--Find strategies for image processing ⋮ Edge-orders ⋮ Farthest neighbors, maximum spanning trees and related problems in higher dimensions ⋮ Simultaneous embedding: edge orderings, relative positions, cutvertices ⋮ A faster algorithm for the two-center decision problem ⋮ Minimizing the sum of diameters efficiently ⋮ Finding the gapped longest common subsequence by incremental suffix maximum queries ⋮ A linear algorithm for MLL proof net correctness and sequentialization ⋮ An implicit representation of chordal comparability graphs in linear time ⋮ Single backup table schemes for shortest-path routing ⋮ Minimizing the density of terminal assignments in layout design ⋮ Alignment-free sequence comparison using absent words ⋮ Scalable parallel algorithms for maximum matching and Hamiltonian circuit in convex bipartite graphs ⋮ On the König deficiency of zero-reducible graphs ⋮ 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 ⋮ Smallest $k$-enclosing rectangle revisited ⋮ Topologically sweeping visibility complexes via pseudotriangulations ⋮ A fast bipartite network flow algorithm for selective assembly ⋮ Efficient Union-Find for planar graphs and other sparse graph classes ⋮ Matching subsequences in trees ⋮ Optimal binary trees with order constraints ⋮ Range minimum queries in minimal space ⋮ A linear-time algorithm for edge-disjoint paths in planar graphs ⋮ Planarity of streamed graphs ⋮ An optimal algorithm for reporting visible rectangles ⋮ Modular decomposition and transitive orientation ⋮ A software package of algorithms and heuristics for disjoint paths in \textit{Pla}nar \textit{Net}works ⋮ Foremost non-stop journey arrival in linear time ⋮ A linear time algorithm for unique Horn satisfiability ⋮ Computing maximum non-crossing matching in convex bipartite graphs ⋮ Disconnectivity and relative positions in simultaneous embeddings ⋮ Linked dynamic tries with applications to LZ-compression in sublinear time and space ⋮ Optimal point movement for covering circular regions ⋮ A theory of alternating paths and blossoms for proving correctness of the $O(\sqrt{V}E)$ general graph maximum matching algorithm ⋮ Complete bound consistency for the global cardinality constraint ⋮ Safety in $s$-$t$ paths, trails and walks ⋮ A data structure for substring-substring LCS length queries ⋮ A formal model for a linear time correctness condition of proof nets of multiplicative linear logic ⋮ A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges ⋮ Sequential and parallel algorithms on compactly represented chordal and strongly chordal graphs ⋮ PROCESSING AN OFFLINE INSERTION-QUERY SEQUENCE WITH APPLICATIONS ⋮ Approximating the Smallest Spanning Subgraph for 2-Edge-Connectivity in Directed Graphs ⋮ Optimal pointer algorithms for finding nearest common ancestors in dynamic trees ⋮ A linear algorithm for the maximal planar subgraph problem ⋮ Deferred-query—An efficient approach for problems on interval and circular-arc graphs ⋮ Linear-Time Approximation for Maximum Weight Matching ⋮ Amortized Computational Complexity ⋮ A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs ⋮ Processing an Offline Insertion-Query Sequence with Applications ⋮ A partially persistent data structure for the set-union problem ⋮ A fast algorithm for the product structure of planar graphs ⋮ On the Power of Tree-Depth for Fully Polynomial FPT Algorithms ⋮ A fast algorithm for quadratic resource allocation problems with nested constraints ⋮ A Faster Algorithm for Computing Maximal $$\alpha $$-gapped Repeats in a String ⋮ Property Suffix Array with Applications in Indexing Weighted Sequences ⋮ Blocking trails for $f$-factors of multigraphs ⋮ A weight-scaling algorithm for $f$-factors of multigraphs ⋮ Non-crossing shortest paths lengths in planar graphs in linear time ⋮ How vulnerable is an undirected planar graph with respect to max flow ⋮ An algorithmic approach to dual integrality of matching and extensions ⋮ Finding Maximum Edge-Disjoint Paths Between Multiple Terminals ⋮ Unnamed Item ⋮ Linear-space S-table algorithms for the longest common subsequence problem ⋮ Non-crossing shortest paths lengths in planar graphs in linear time ⋮ Partial and simultaneous transitive orientations via modular decompositions ⋮ An $O(n+m)$ certifying triconnnectivity algorithm for Hamiltonian graphs ⋮ An almost quadratic time algorithm for sparse spliced alignment ⋮ How vulnerable is an undirected planar graph with respect to max flow ⋮ Routing equal-size messages on a slotted ring ⋮ The longest common substring problem ⋮ Dynamic 3-sided planar range queries with expected doubly-logarithmic time ⋮ Unnamed Item ⋮ Simple and efficient LZW-compressed multiple pattern matching ⋮ The Optimal Alphabetic Tree problem revisited ⋮ Greedy Shortest Common Superstring Approximation in Compact Space ⋮ Optimal shooting: Characterizations and applications ⋮ Minimum dominating sets of intervals on lines ⋮ An optimal time and minimal space algorithm for rectangle intersection problems ⋮ Multicommodity flows in cycle graphs ⋮ Fast incremental planarity testing ⋮ Maintenance of triconnected components of graphs ⋮ A new metric between polygons, and how to compute it ⋮ Optimal parallel algorithm for shortest-paths problem on interval graphs ⋮ A Decomposition Algorithm for Nested Resource Allocation Problems ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ Computing runs on a trie ⋮ Smallest k-enclosing rectangle revisited ⋮ Computing the Antiperiod(s) of a String ⋮ Mondshein Sequences (a.k.a. (2,1)-Orders) ⋮ A Linear-Time Algorithm for Seeds Computation ⋮ Linear Algorithms for Chordal Graphs of Bounded Directed Vertex Leafage ⋮ Path problems in skew-symmetric graphs ⋮ The Power of Linear-Time Data Reduction for Maximum Matching ⋮ Algorithms for Weighted Matching Generalizations II: f-factors and the Special Case of Shortest Paths ⋮ Unnamed Item ⋮ Drawing Tree-Based Phylogenetic Networks with Minimum Number of Crossings ⋮ Linear time algorithms for graph search and connectivity determination on complement graphs. ⋮ Inferring regular languages by merging nonterminals ⋮ Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs

Cites Work