A Class of Algorithms which Require Nonlinear Time to Maintain Disjoint Sets

No abstract is available for this paper.

• Publication year

  1979

• Venue

  Journal of computer and system sciences (Print)

• Publication date

  1979-04-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/0022-0000(79)90042-4
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Applications of Path Compression on Balanced Trees

  1979cited by this paper
• The Expected Linearity of a Simple Equivalence Algorithm

  1978cited by this paper
• On Recognizing Graph Properties from Adjacency Matrices

  1976cited by this paper
• Linear Expected Time of a Simple Union-Find Algorithm

  1976cited by this paper
• The intrinsically exponential complexity of the circularity problem for attribute grammars

  1975cited by this paper
• The computational complexity of algebraic and numeric problems

  1975cited by this paper
• Solving path problems on directed graphs.

  1975cited by this paper
• The Design and Analysis of Computer Algorithms

  1974cited by this paper
• SUPER-EXPONENTIAL COMPLEXITY OF PRESBURGER ARITHMETIC

  1974cited by this paper
• REAL-TIME SIMULATION OF MULTIDIMENSIONAL TURING MACHINES BY STORAGE MODIFICATION MACHINES

  1973cited by this paper
• Set Merging Algorithms

  1973cited by this paper
• Efficiency of Equivalence Algorithms

  1972cited by this paper
• Efficiency of a Good But Not Linear Set Union Algorithm

  1972cited by this paper
• The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space

  1972cited by this paper
• An improved equivalence algorithm

  1964cited by this paper

• Error Correction Algorithms for Efficient Gene Expression Quantification in Single Cell Transcriptomics

  2026cites this paper
• How to go from partial to full retroactivity in detail

  2025cites this paper
• Topological Alignment of Shared Vision-Language Embedding Space

  2025cites this paper
• On the Asymmetrical Nature of Entity Matching Using Pre-Trained Transformers

  2025cites this paper
• Collaborative Imputation for Multivariate Time Series with Convergence Guarantee

  2025cites this paper
• Pipelining Kruskal's: A Neuromorphic Approach for Minimum Spanning Tree

  2025cites this paper
• Fully-Adaptive Dynamic Connectivity of Square Intersection Graphs

  2024cites this paper
• Advances in ArborX to support exascale applications

  2024influential citation
• A computational implementation of Vector-based 3D Graphic Statics (VGS) for interactive and real-time structural design

  2024cites this paper
• Clausal Congruence Closure

  2024cites this paper
• An Effective Branch-and-Bound Algorithm with New Bounding Methods for the Maximum s-Bundle Problem

  2024cites this paper
• From Motif to Path: Connectivity and Homophily

  2024cites this paper
• Low-Latency Sliding Window Connectivity

  2024cites this paper
• Incremental Sliding Window Connectivity over Streaming Graphs

  2024cites this paper
• PHLP: Sole Persistent Homology for Link Prediction - Interpretable Feature Extraction

  2024cites this paper
• Fast Density-Based Clustering: Geometric Approach

  2023cites this paper
• An Augmented Index-based Efficient Community Search for Large Directed Graphs

  2023cites this paper
• Label-efficient Segmentation via Affinity Propagation

  2023cites this paper
• Simpler Analyses of Union-Find

  2023cites this paper
• Super Sparse 3D Object Detection

  2023cites this paper
• Rectangle Stabbing and Orthogonal Range Reporting Lower Bounds in Moderate Dimensions

  2022cites this paper
• 4D Range Reporting in the Pointer Machine Model in Almost-Optimal Time

  2022cites this paper
• Flooding Topology Algorithms for Computer Networks

  2022cites this paper
• GriT-DBSCAN: A Spatial Clustering Algorithm for Very Large Databases

  2022cites this paper
• LGRASS: Linear Graph Spectral Sparsification for Final Task of the 3rd ACM-China International Parallel Computing Challenge

  2022cites this paper
• CFL/Dyck Reachability

  2022cites this paper
• Enumerating Regular Languages with Bounded Delay

  2022cites this paper
• Top tree compression of tries. (English)

  2022cites this paper
• Enumerating Regular Languages in Constant Delay

  2022cites this paper
• Fast characterization of segmental duplication structure in multiple genome assemblies

  2022cites this paper
• Dynamic Membership for Regular Languages

  2021cites this paper
• Integer Programming Formulations for Minimum Spanning Tree Interdiction

  2021cites this paper
• Preprocessing in SAT Solving

  2021cites this paper
• Implicit Incremental Model Analyses and Transformations

  2021cites this paper
• Fast tree-based algorithms for DBSCAN on GPUs

  2021cites this paper
• Near-Optimal Spanners for General Graphs in (Nearly) Linear Time

  2021cites this paper
• Range Minimum Queries in Minimal Space

  2021cites this paper
• Computing the 4-Edge-Connected Components of a Graph in Linear Time

  2021cites this paper
• Fast tree-based algorithms for DBSCAN for low-dimensional data on GPUs

  2021cites this paper
• Exact algorithms for the multi-compartment vehicle routing problem with flexible compartment sizes

  2021cites this paper
• Reliability and importance measure analysis of networks with shared risk link groups

  2021cites this paper
• A Scalable Concurrent Algorithm for Dynamic Connectivity

  2021cites this paper
• Compression by Contracting Straight-Line Programs

  2021cites this paper
• Topological Regularization for Dense Prediction

  2021cites this paper
• Explainable Deep Behavioral Sequence Clustering for Transaction Fraud Detection

  2021cites this paper
• N-cluster correlations in four- and five-dimensional percolation

  2020cites this paper
• An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in ℝ3

  2020cites this paper
• A Lower Bound for Dynamic Fractional Cascading

  2020cites this paper
• Financial table extraction in image documents

  2020cites this paper
• Asymptotic Analysis of a Direct Algorithm for Synthesizing a Minimal Joint Graph

  2020cites this paper
• The Algorithm Design Manual

  2020cites this paper
• RandomLink - Avoiding Linkage-Effects by Employing Random Effects for Clustering

  2020cites this paper
• Efficient Community Search over Large Directed Graph: An Augmented Index-based Approach

  2020cites this paper
• Exact solution of the soft-clustered vehicle-routing problem

  2020cites this paper
• Pointer-Machine Algorithms for Fully-Online Construction of Suffix Trees and DAWGs on Multiple Strings

  2020cites this paper
• Ripser: efficient computation of Vietoris–Rips persistence barcodes

  2019cites this paper
• In Search of the Fastest Concurrent Union-Find Algorithm

  2019cites this paper
• Top Tree Compression of Tries

  2019cites this paper
• Correlation-Based Community Detection

  2019cites this paper
• Time-Sync Video Tag Extraction Using Semantic Association Graph

  2019cites this paper
• A New Lower Bound for Semigroup Orthogonal Range Searching

  2019cites this paper
• Covering Polygons by Min-Area Convex Polygons

  2019influential citation
• An extensible approach to implicit incremental model analyses

  2019cites this paper
• Polytopes associated with symmetry handling

  2018cites this paper
• Heuristic algorithms for the Maximum Colorful Subtree problem

  2018cites this paper
• A Constructive Arboricity Approximation Scheme

  2018cites this paper
• Network Control Plane Synthesis and Verification

  2018cites this paper
• Improved collective influence of finding most influential nodes based on disjoint-set reinsertion

  2018cites this paper
• High Performance Density-Based Clustering on Massive Data

  2017cites this paper
• Deduplication in a massive clinical note dataset

  2017cites this paper
• On the algorithmic aspects of Turán's Theorem

  2017cites this paper
• Almost-linear time decoding algorithm for topological codes

  2017cites this paper
• On the Hardness and Approximation of Euclidean DBSCAN

  2017cites this paper
• Optimal Dyck reachability for data-dependence and alias analysis

  2017influential citation
• In-Memory Storage for Labeled Tree-Structured Data

  2017cites this paper
• Data Structure Lower Bounds for Document Indexing Problems

  2016cites this paper
• Compressing Trees with a Sledgehammer

  2016cites this paper
• Deletion Without Rebalancing in Binary Search Trees

  2016cites this paper
• Methoden zur Bildsegmentation und zum Connected Component Labeling auf einem FPGA für eine zukünftige On-Board Bilddatenverarbeitung

  2016influential citation
• Tight(er) bounds for similarity measures, smoothed approximation and broadcasting

  2016cites this paper
• Exploring the Problem Space of Orthogonal Range Searching

  2015cites this paper
• The Batched Predecessor Problem in External Memory

  2014cites this paper
• Optimal Decremental Connectivity in Planar Graphs

  2014cites this paper
• Pardicle: Parallel Approximate Density-Based Clustering

  2014cites this paper
• Algorithm Design and Applications

  2014cites this paper
• Scalable parallel OPTICS data clustering using graph algorithmic techniques

  2013cites this paper
• Dynamic Data Structures: The Interplay of Invariants and Algorithm Design

  2013cites this paper
• Dominators in Directed Graphs : A Survey of Recent Results , Applications , and Open Problems

  2013cites this paper
• Space-Efficient Data Structures in the Word-RAM and Bitprobe Models

  2013cites this paper
• A new scalable parallel DBSCAN algorithm using the disjoint-set data structure

  2012cites this paper
• Improved range searching lower bounds

  2012cites this paper
• Scalable and distributed methods for entity matching, consolidation and disambiguation over linked data corpora

  2012cites this paper
• An Optimal Dynamic Data Structure for Stabbing-Semigroup Queries

  2012cites this paper
• Capítulo 3 – Árvores

  2012cites this paper
• Higher-dimensional orthogonal range reporting and rectangle stabbing in the pointer machine model

  2012cites this paper
• Don't rush into a union: take time to find your roots

  2011cites this paper
• A Dynamic Stabbing-Max Data Structure with Sub-Logarithmic Query Time

  2011cites this paper
• Path Queries in Weighted Trees

  2011cites this paper
• I/O-efficient batched union-find and its applications to terrain analysis

  2010cites this paper
• Low-Entropy Computational Geometry

  2010cites this paper